Python 实现查找两个字符串的最长公共子串

可以使用动态规划来解决查找两个字符串 'a', 'b' 中的最长公共子串的问题。具体步骤如下：

1. 创建一个二维数组 'dp'，其中 'dp[i][j]' 表示以字符串 'a' 的第 'i' 个字符和字符串 'b' 的第 'j' 个字符为结尾的最长公共子串的长度。
2. 初始化 'dp' 的第一行和第一列为 0，表示以字符串 'a' 的第 0 个字符和字符串 'b' 的第 0 个字符为结尾的最长公共子串的长度为 0。
3. 遍历字符串 'a' 和字符串 'b' 的每个字符，如果当前字符相等，则 'dp[i][j] = dp[i-1][j-1] + 1'，表示以当前字符为结尾的最长公共子串的长度等于前一个字符为结尾的最长公共子串的长度加 1；如果当前字符不相等，则 'dp[i][j] = 0'，表示以当前字符为结尾的最长公共子串的长度为 0。
4. 在遍历的过程中，记录最长公共子串的长度和结束位置，并更新最长公共子串的长度和结束位置。
5. 根据最长公共子串的结束位置和长度，可以得到最长公共子串。
6. 返回最长公共子串。

下面是 Python 的实现代码：

def longest_common_substring(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n+1) for _ in range(m+1)]
    max_length = 0
    end_index = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_index = i - 1

    return a[end_index-max_length+1:end_index+1]

使用示例：

a = 'ABCD'
b = 'ABD'
print(longest_common_substring(a, b))  # 输出 'AB'

这段代码的时间复杂度为 O(m*n)，其中 'm' 和 'n' 分别是字符串 'a' 和字符串 'b' 的长度。