使用自底向上的动态规划查找最长公共子串的Python程序

什么是最长公共子串？

最长公共子串是指在两个字符串中，长度最长且连续出现的相同子串。例如，字符串 “abcdefg” 和 “xyzabcde” 的最长公共子串为 “abcde”。

动态规划方法求解最长公共子串

动态规划方法可以用于寻找最长公共子串，其时间复杂度为 $O(mn)$ ，其中 $m$ 和 $n$ 分别是两个字符串的长度。具体方法如下：

首先建立一个 $m \times n$ 的矩阵 $DP$ ，给予初始值 $DP_{i,j} = 0$ 。然后从两个字符串的第一个字符开始遍历，如果 $string1_i$ 等于 $string2_j$ ，则将 $DP_{i,j}$ 的值设为 $DP_{i-1, j-1} + 1$ 。否则， $DP_{i,j}$ 的值为 0。

在遍历的过程中，记录当前最大的 $DP_{i,j}$ 的值，并记录下标。最后从该下标开始向前取 $DP_{i,j}$ 的值，即为最长公共子串。

下面是使用Python实现自底向上的动态规划方法查找最长公共子串的程序：

def longest_common_substring(string1, string2):
    m, n = len(string1), len(string2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len, max_end = 0, 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if string1[i-1] == string2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    max_end = i
            else:
                dp[i][j] = 0
    return string1[max_end-max_len: max_end]

string1 = "abcdefg"
string2 = "xyzabcde"
print(longest_common_substring(string1, string2)) # 输出 "abcde"