深入解析最长公共子串

什么是最长公共子串

最长公共子串（Longest Common Substring）是指两个或多个字符串中最长的子串，它可以用来比较两个字符串的相似程度。

例如，对于字符串 "abcdefg" 和 "defghij"，它们的最长公共子串为 "defg"，长度为 4。即 "abcdefg" 中的 "defg" 与 "defghij" 中的 "defg" 相同。

暴力解法

最简单的方法就是暴力枚举，我们依次枚举字符串 S1 和 S2 中的每个子串，然后判断该子串是否为它们的公共子串。最后找到长度最长的那个子串。

最坏时间复杂度为 $O(n^3)$，不适合处理大规模数据。

下面是暴力解法的伪代码：

for i from 0 to len(S1)
    for j from 0 to len(S2)
        for k from 0 to len(S1) - i and len(S2) - j
            if S1[i:i+k] == S2[j:j+k] and k > ans
                ans = k
                lcs = S1[i:i+k]
return lcs

动态规划解法

动态规划是一种时间复杂度为 $O(n^2)$ 的解法，它把问题拆解成若干个子问题，然后通过求解子问题的最优解，得到原问题的最优解。

对于字符串 S1 和 S2，我们定义二维数组 dp，其中 dp[i][j] 表示 S1[0:i] 和 S2[0:j] 的最长公共子串长度。

如果 S1[i] == S2[j]，那么 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = 0。

下面是动态规划解法的伪代码：

dp = [[0 for _ in range(len(S2))] for _ in range(len(S1))]
ans = 0
lcs = ''
for i from 0 to len(S1)
    for j from 0 to len(S2)
        if S1[i] == S2[j]
            if i == 0 or j == 0
                dp[i][j] = 1
            else
                dp[i][j] = dp[i-1][j-1] + 1
        if dp[i][j] > ans
            ans = dp[i][j]
            lcs = S1[i-ans+1:i+1]
return lcs

示例解释

示例1

假设有字符串 S1 和 S2 分别为 "abcde" 和 "bcdfg"，它们的最长公共子串为 "bcd"，长度为 3。我们可以运用暴力解法和动态规划解法来进行验证。

暴力解法的伪代码为：

for i from 0 to len(S1)
    for j from 0 to len(S2)
        for k from 0 to len(S1) - i and len(S2) - j
            if S1[i:i+k] == S2[j:j+k] and k > ans
                ans = k
                lcs = S1[i:i+k]
return lcs

按照该算法步骤，有：

当 i=0, j=0, k=1 时，k=1, ans=1, lcs='a'；

当 i=0, j=1, k=1 时，k=1, ans=1, lcs='b'；

当 i=0, j=2, k=1 时，k=1, ans=1, lcs='c'；

当 i=0, j=3, k=1 时，k=1, ans=1, lcs='d'；

当 i=0, j=4, k=1 时，k=1, ans=1, lcs='e'；

当 i=1, j=0, k=1 时，k=1, ans=1, lcs='b'；

当 i=1, j=1, k=3 时，k=3, ans=3, lcs='bcd'；

当 i=1, j=2, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=1, j=3, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=2, j=0, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=2, j=1, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=2, j=2, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=3, j=0, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=3, j=1, k=1 时，k=1, ans=3, lcs='bcd'；

当 i=4, j=0, k=1 时，k=1, ans=3, lcs='bcd'；

最后得到 lcs='bcd'。

动态规划解法的伪代码为：

dp = [[0 for _ in range(len(S2))] for _ in range(len(S1))]
ans = 0
lcs = ''
for i from 0 to len(S1)
    for j from 0 to len(S2)
        if S1[i] == S2[j]
            if i == 0 or j == 0
                dp[i][j] = 1
            else
                dp[i][j] = dp[i-1][j-1] + 1
        if dp[i][j] > ans
            ans = dp[i][j]
            lcs = S1[i-ans+1:i+1]
return lcs

按照该算法步骤，有：

当 i=0, j=0, S1[i]='a', S2[j]='b' 时，dp[0][0]=0；

当 i=0, j=1, S1[i]='a', S2[j]='c' 时，dp[0][1]=0；

当 i=0, j=2, S1[i]='a', S2[j]='d' 时，dp[0][2]=0；

当 i=0, j=3, S1[i]='a', S2[j]='e' 时，dp[0][3]=0；

当 i=0, j=4, S1[i]='a', S2[j]='f' 时，dp[0][4]=0；

当 i=1, j=0, S1[i]='b', S2[j]='b' 时，dp[1][0]=1；

当 i=1, j=1, S1[i]='b', S2[j]='c' 时，dp[1][1]=0；

当 i=1, j=2, S1[i]='b', S2[j]='d' 时，dp[1][2]=1；

当 i=1, j=3, S1[i]='b', S2[j]='e' 时，dp[1][3]=0；

当 i=1, j=4, S1[i]='b', S2[j]='f' 时，dp[1][4]=0；

当 i=2, j=0, S1[i]='c', S2[j]='b' 时，dp[2][0]=0；

当 i=2, j=1, S1[i]='c', S2[j]='c' 时，dp[2][1]=1；

当 i=2, j=2, S1[i]='c', S2[j]='d' 时，dp[2][2]=0；

当 i=2, j=3, S1[i]='c', S2[j]='e' 时，dp[2][3]=0；

当 i=2, j=4, S1[i]='c', S2[j]='f' 时，dp[2][4]=0；

当 i=3, j=0, S1[i]='d', S2[j]='b' 时，dp[3][0]=0；

当 i=3, j=1, S1[i]='d', S2[j]='c' 时，dp[3][1]=0；

当 i=3, j=2, S1[i]='d', S2[j]='d' 时，dp[3][2]=1；

当 i=3, j=3, S1[i]='d', S2[j]='e' 时，dp[3][3]=0；

当 i=3, j=4, S1[i]='d', S2[j]='f' 时，dp[3][4]=0；

当 i=4, j=0, S1[i]='e', S2[j]='b' 时，dp[4][0]=0；

当 i=4, j=1, S1[i]='e', S2[j]='c' 时，dp[4][1]=0；

当 i=4, j=2, S1[i]='e', S2[j]='d' 时，dp[4][2]=0；

当 i=4, j=3, S1[i]='e', S2[j]='e' 时，dp[4][3]=0；

当 i=4, j=4, S1[i]='e', S2[j]='f' 时，dp[4][4]=0；

最后得到 lcs='bcd'。

总结

动态规划解法是最长公共子串问题的高效解法，与暴力枚举法不同，它通过解决子问题的最优解，得到原问题的最优解。但是，用动态规划求解的空间和时间复杂度都比较高，如果 S1 和 S2 的长度较大，则需要引入优化、精简算法等措施处理。

如有问题，欢迎指正。