最长公共子串（Longest Common Substring）问题

最长公共子串问题是寻找两个或多个字符串中最长的连续公共子串。与最长公共子序列（LCS）不同，子串要求字符必须是连续的。这个问题在生物信息学（如DNA序列比对）和文本相似度比较中有广泛应用。

问题描述

给定两个字符串 text1 和 text2，找出它们的最长公共子串（LCS）。例如：

• text1 = "ABCDGH", text2 = "ACDGHR"，最长公共子串是 "CDGH"，长度为4。

关键思路

使用动态规划（DP）来记录匹配状态。定义一个二维数组 dp[i][j]，表示以 text1[i-1] 和 text2[j-1] 结尾的公共子串的长度（索引从0开始）。状态转移规则如下：

• 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1（连续匹配延长子串）。
• 否则，dp[i][j] = 0（不匹配时子串长度重置为0）。

最终，遍历 dp 数组找到最大值，即为最长公共子串的长度。

详细步骤

1. 初始化DP表：

   • 创建大小为 (len(text1)+1) x (len(text2)+1) 的二维数组 dp，初始值全为0。
   • 多出一行一列用于处理边界情况（空字符串）。

2. 填充DP表：

   • 遍历 i 从1到 len(text1)，j 从1到 len(text2)：
     • 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
     • 否则，dp[i][j] = 0。
   • 同时记录最大长度 max_len 和对应的结束位置 end_index（在 text1 中的索引）。

3. 构造结果：

   • 根据 max_len 和 end_index，从 text1 中提取子串：text1[end_index - max_len : end_index]。

示例演示

以 text1 = "ABCDGH", text2 = "ACDGHR" 为例：

• DP表填充后如下（省略全0行和列）：

        A  C  D  G  H  R
    A [1, 0, 0, 0, 0, 0]
    B [0, 0, 0, 0, 0, 0]
    C [0, 1, 0, 0, 0, 0]
    D [0, 0, 2, 0, 0, 0]
    G [0, 0, 0, 3, 0, 0]
    H [0, 0, 0, 0, 4, 0]
  

• 最大长度 max_len = 4，结束位置 end_index = 5（对应 text1[1:5]，即 "CDGH"）。

复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 为两个字符串的长度。
• 空间复杂度：O(mn)，可优化至 O(min(m, n))（只保留前一行的DP值）。

优化方向

• 空间优化：由于 dp[i][j] 仅依赖上一行 dp[i-1][j-1]，可改用一维数组滚动更新。
• 早期终止：如果剩余字符数不足以更新 max_len，可提前结束循环。

通过以上步骤，你可以高效解决最长公共子串问题，并理解其与LCS问题的核心区别（连续性要求）。