最长公共子串

最长公共子串问题是寻找两个字符串的最长公共子串的问题。

最长公共子串和最长公共子序列之间有一个区别。对于子串，子串中的所有字符在原始字符串中必须是连续的，并且子串中的字符顺序应与字符串中的顺序相同。对于子序列，我们可以省略一些字符，这意味着子串中的字符不一定是连续的。

让我们通过一个例子来理解。

考虑下面两个字符串

S1: a b c d a f

S2: b c d f

比较上面的两个字符串，我们会发现

最长公共子串是 bcd。

最长公共子序列是 bcdf。

例如：下面给出两个字符串

S1: ABABCD

S2: BABCDA

比较上面的两个字符串，我们会发现 BABCD 是最长公共子串。

如果我们有很长的字符串，那么找到最长公共子串将不可行。所以，我们使用动态规划方法来解决这个问题。

算法

考虑下面两个字符串

S1: a b c d a f

S2: z b c d f

从上面的表格中我们可以看出，第一行代表第一个字符串，即 S1，第一列代表第二个字符串，即 S2。

当 i=0，j =0 时，S1[i]= z，S2[j] = a

由于 S1[i] 和 S2[j] 之间没有公共字符串，因此最长公共子串的长度为 0。

当 i=0，j=1 时，S1[i] = z，S2[j] = ab

当 i=0，j=2 时，S1[i] = z，S2[j] = abc

当 i=0，j = 3 时，S1[i] = z，S2[j] = abcd

类似地，我们将填充其他两列，表格将是

当 i=1，j=0 时，S1[1] = b，S2[0] = a

当 i=1，j=1 时，S1[1] = b，S2[1] = b

由于 S1[1] 和 S2[1] 之间有一个公共子串，即 b，因此最长公共子串的长度为 1，如下所示

当 i=1，j=2 时，S1[1] = b，S2[2] = c

由于 'b' 和 'c' 不相同，所以在 S[1][2] 中填 0。

当 i=1，j=3 时，S1[1] = b，S2[3] = d

由于 'b' 和 'd' 不相同，所以在 S[1][3] 中填 0。

当 i=1，j= 4 时，S1[1] = b，S2[4] = a

当 i=1，j=5 时，S1[1] = b，S2[5] = f

由于 'b' 和 'f' 不相同，所以在 S[1][5] 中填 0。

当 i=2，j= 0 时，S1[2] = c 和 S2[5] = a

由于 'c' 和 'a' 不相同，所以在 S[2][0] 中填 0。

当 i=2，j = 1 时，S1[2] = 'c' 和 S2[1] = 'b'

由于 'c' 和 'b' 不相同，所以在 S[2][1] 中填 0。

当 i=2，j=2 时，S1[2] = 'c' 和 S2[2] = 'c'

由于两个字符 'c' 都相同；因此，"bc" 是字符串 "zbc" 和 "abc" 之间的公共子串。最长公共子串的长度为 2。

当 i=2，j=3 时，S1[2] = 'c' 和 S2[3] = 'd'

由于 'c' 和 'd' 不相同，所以在 S[2][3] 中填 0。

当 i=2，j=4 时，S1[2] = 'c' 和 S2[4] = 'a'

由于 'c' 和 'a' 不相同，所以在 S[2][4] 中填 0。

当 i=2，j=5 时，S1[2] = 'c' 和 S2[5] = 'f'

由于 'c' 和 'f' 不同，所以在 S[2][5] 中填 0。

当 i=3，j=0 时，S1[3] = 'd' 和 S2[0] = 'a'

由于 'd' 和 'a' 不同，所以在 S[3][0] 中填 0。

当 i=3，j=1 时，S1[3] = 'd' 和 S2[1] = 'b'

由于 'd' 和 'b' 不相同，所以在 S[3][1] 中填 0。

当 i=3，j=2 时，S1[3] = 'd' 和 S2[2] = 'c'

由于 'd' 和 'c' 不相同，所以在 S[3][2] 中填 0。

当 i=3，j=3 时，S1[3] = 'd' 和 S2[3] = 'd'

由于两个字符，即 'd' 都相同；因此，'bcd' 是字符串 'abcd' 和 'zbcd' 之间的公共子串。最长公共子串的长度为 3。

类似地，我们将计算另外两列的值，即 S[3][4] 和 S[3][5]，如下表所示

最终表格将是

从上面的表格中我们可以看出，最长公共子串的长度是 3。我们也可以从上面的表格中找到最长公共子串。首先，我们移动到具有最高值的列，即 3，与 3 对应的字符是 'd'，然后我们沿着 3 对角线移动，数字是 2。与 2 对应的字符是 'c'，我们再次沿着 2 对角线移动，值为 1。与 1 值对应的字符是 'b'。因此，子串将是 "bcd"。