如何高效计算两个字符串的最长公共子串长度？

你的动态规划解法是解决最长公共子串问题的经典方案，时间复杂度为O(n*m)（n、m分别为s1、s2的长度），对于1000字符的输入，1e6次计算完全在可接受范围内，不过确实有空间优化的余地，也存在时间复杂度更优的替代方法。

一、现有DP解法的空间优化 #

原二维DP数组中，每个dp[i][j]仅依赖于左上角的dp[i-1][j-1]，因此可以用一维数组将空间复杂度从O(n*m)降至O(min(n,m))。核心是从后往前遍历较短字符串的维度，避免覆盖上一轮需要的计算值：

def longestCommonSubstring(s1, s2):
    # 确保s2为较短字符串，最小化一维数组长度
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    dp = [0] * (len(s2) + 1)
    max_len = 0
    for i in range(1, len(s1) + 1):
        # 逆序遍历，防止覆盖上一轮的dp[j-1]
        for j in range(len(s2), 0, -1):
            if s1[i-1] == s2[j-1]:
                dp[j] = dp[j-1] + 1
                max_len = max(max_len, dp[j])
            else:
                dp[j] = 0
    return max_len

优化后内存占用从1e6级别降至1e3级别，时间复杂度保持不变，对于1000字符的输入性能几乎无差别，但处理更大规模输入时优势明显。

二、时间复杂度更优的方法 #

1. 滑动窗口+滚动哈希（推荐平衡性能与实现复杂度） #

通过二分答案+滚动哈希的组合，可将时间复杂度降至O((n+m)*log(min(n,m)))：

• 二分范围：最长公共子串长度的可能值为0到min(n,m)
• 检查逻辑：对于假设的长度k，计算s1中所有长度为k的子串的哈希值并存入集合，再遍历s2的所有长度为k的子串，检查哈希值是否存在于集合中（若存在则说明存在长度为k的公共子串）
• 哈希碰撞处理：可使用双哈希（两种不同的哈希函数）或在哈希值匹配时直接比较原字符串，避免误判

该方法对于1000字符的输入，计算量仅为约1e4次，比DP更快，且实现难度低于后缀数组。

2. 后缀数组法（极致性能） #

将两个字符串用一个唯一分隔符拼接（如s1 + "#" + s2），构建后缀数组后，找到相邻后缀中最长的公共前缀，且这两个后缀分别来自s1和s2，该前缀长度即为答案。构建后缀数组的线性时间算法可将总时间复杂度降至O(n+m)，但实现细节繁琐（需处理后缀排序、最长公共前缀数组等），对于1000字符的输入，性价比不如DP或滑动窗口法。

总结 #

针对你的1000字符需求，优化后的一维DP解法是最优选择——实现简单、不易出错，性能完全达标；若追求极致性能或处理更大规模输入，可考虑滑动窗口+滚动哈希方案；后缀数组法则适合对时间复杂度有严格要求的场景。

内容的提问来源于stack exchange，提问作者nikhil pachange