最长公共子串问题

题目描述
最长公共子串（Longest Common Substring）问题要求找出两个字符串中最长的连续公共子串。与最长公共子序列（LCS）不同，子串必须是连续的。例如，字符串"ABABC"和"BABCA"的最长公共子串是"BABC"，长度为4。

解题思路

1. 暴力解法：枚举一个字符串的所有子串，检查是否在另一个字符串中出现。时间复杂度为O(n^2 * m)，效率低。
2. 动态规划解法：利用二维数组记录以两个字符串当前位置结尾的公共子串长度，通过状态转移避免重复计算。
3. 后缀数组/自动机优化：更高效的算法，但实现复杂，面试中通常以动态规划为准。

动态规划解法详解
步骤1：定义状态
设dp[i][j]表示以字符串s1的第i个字符和s2的第j个字符结尾的最长公共子串的长度。注意：这里i和j是字符索引（从1开始计数），实际代码中需调整下标。

步骤2：状态转移方程

• 若s1[i-1] == s2[j-1]（字符匹配），则dp[i][j] = dp[i-1][j-1] + 1。
• 若字符不匹配，则dp[i][j] = 0（因为子串必须连续，不匹配时当前公共子串长度重置为0）。

步骤3：初始化

• 当i=0或j=0时，表示一个字符串为空，此时dp[0][j]或dp[i][0]均为0。

步骤4：记录结果
在填充dp表时，同步记录最大的dp[i][j]值及其结束位置，即可回溯得到最长公共子串。

示例演示
以s1="ABABC"，s2="BABCA"为例：

1. 创建dp表，维度为(len(s1)+1) x (len(s2)+1)，初始化第一行和第一列为0。
2. 逐行填充：
   • i=1, j=1：s1[0]='A' vs s2[0]='B'，不匹配，dp[1][1]=0。
   • i=2, j=1：s1[1]='B' vs s2[0]='B'，匹配，dp[2][1]=dp[1][0]+1=1。
   • 继续填充，当i=4, j=4时，s1[3]='B' vs s2[3]='B'，匹配，且dp[4][4]=dp[3][3]+1=3。
   • 最终最大值为dp[5][5]=4（对应子串"BABC"）。

优化技巧

• 空间优化：由于dp[i][j]仅依赖上一行数据，可将二维数组压缩为一维数组，空间复杂度从O(n*m)降至O(min(n, m))。
• 提前终止：若当前剩余字符数已无法超过已记录的最大长度，可提前结束循环。

代码实现（简化版）

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len, end_pos = 0, 0  # 记录最长子串长度及其在s1中的结束位置
    
    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] > max_len:
                    max_len = dp[i][j]
                    end_pos = i  # 记录s1中的结束位置
            else:
                dp[i][j] = 0  # 不匹配时重置
    
    return s1[end_pos - max_len:end_pos]  # 根据结束位置和长度截取子串

总结
最长公共子串问题通过动态规划将时间复杂度优化至O(n*m)，是面试中考察二维动态规划建模能力的经典题目。关键点在于理解状态定义中“以当前位置结尾”的约束条件，以及连续性的处理方式。