求两个字符串的最长公共子串

可以使用动态规划来解决最长公共子串的问题。

假设给出两个字符串 $s1$ 和 $s2$，用 $dp[i][j]$ 表示以 $s1$ 的第 $i$ 个字符和 $s2$ 的第 $j$ 个字符为结尾的最长公共子串的长度。

当 $s1[i] \neq s2[j]$ 时，$dp[i][j]$ 应该为 0，因为以这两个字符结尾的字符串不可能有公共子串。

当 $s1[i] = s2[j]$ 时，$dp[i][j]$ 应该为 $dp[i-1][j-1] + 1$，因为以这两个字符结尾的字符串可能有公共子串，并且公共子串的长度就是 $dp[i-1][j-1]$ 加上 1。

最终的答案就是 $dp[i][j]$ 中的最大值。

下面是该问题的 Python 代码实现：

def longest_common_substring(s1, s2):
    n1, n2 = len(s1), len(s2)
    dp = [[0] * (n2+1) for _ in range(n1+1)]
    ans = 0
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
    return ans

时间复杂度为 $O(n_1n_2)$，其中 $n_1$ 和 $n_2$ 分别是两个字符串的长度。