String算法找出两个字符串中共有的最大部分

一种常见的方法是使用动态规划。

首先，建立一个二维数组，行表示第一个字符串的字符，列表示第二个字符串的字符。数组中的元素表示第一个字符串中以该行字符结尾的子串和第二个字符串中以该列字符结尾的子串的最长公共子串的长度。

然后，遍历两个字符串，对于每个字符，如果它们相等，则将对应的数组元素设为左上角元素加1，否则将对应的数组元素设为0。

最后，找出数组中最大的元素，即为两个字符串中共有的最大部分的长度。如果需要找出具体的最长公共子串，可以根据数组中最大元素的位置逆推回去。

以下是Python代码实现：

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    longest = 0
    longest_end = 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > longest:
                    longest = dp[i][j]
                    longest_end = i
            else:
                dp[i][j] = 0
    return s1[longest_end - longest:longest_end]

其中，变量longest表示最长公共子串的长度，变量longest_end表示最长公共子串在第一个字符串中的结束位置。数组dp中的元素表示第一个字符串中以该行字符结尾的子串和第二个字符串中以该列字符结尾的子串的最长公共子串的长度。最后，返回第一个字符串中最长公共子串的位置及其长度。