python 两字符串公共字符串

要找出两个字符串的公共子字符串，可以使用动态规划的方法来解决。

首先，我们定义一个二维数组dp来记录子字符串的匹配情况。dp[i][j]表示以第一个字符串的第i个字符结尾和第二个字符串的第j个字符结尾的最长公共子字符串的长度。

然后，我们遍历两个字符串的所有字符，当第一个字符串的第i个字符等于第二个字符串的第j个字符时，说明找到了一个匹配的字符，我们将dp[i][j]更新为dp[i-1][j-1] + 1。否则，若两个字符不匹配，dp[i][j]就保持为0。

遍历完所有的字符之后，我们再次遍历dp数组，找到其中最大的值，即为两个字符串的最长公共子字符串的长度。

最后，我们可以通过切片的方式，提取出最长公共子字符串。

下面是具体的Python代码：

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
    max_len = 0
    end = 0
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end = i
    
    longest_common = str1[end-max_len:end]
    return longest_common

这样，我们就可以得到两个字符串的最长公共子字符串。