最长公共子串（Longest Common Substring）

我将为您详细讲解最长公共子串问题，这是一个经典的线性动态规划问题。

问题描述

给定两个字符串s1和s2，找到它们的最长公共子串。公共子串要求是连续的字符序列。

示例：

• s1 = "abcde", s2 = "abfce"
• 最长公共子串为 "ab" 或 "ce"，长度为2

解题思路

基本概念理解

首先需要区分最长公共子串和最长公共子序列：

• 子串：必须连续
• 子序列：可以不连续

动态规划解法

步骤1：定义状态
定义dp[i][j]为以s1的第i个字符和s2的第j个字符结尾的最长公共子串的长度。

步骤2：状态转移方程

• 如果s1[i-1] == s2[j-1]：
  dp[i][j] = dp[i-1][j-1] + 1
• 如果s1[i-1] != s2[j-1]：
  dp[i][j] = 0

步骤3：初始化

• dp[0][j] = 0 (空字符串与任何字符串的公共子串长度为0)
• dp[i][0] = 0 (任何字符串与空字符串的公共子串长度为0)

步骤4：填充DP表
让我们通过一个具体例子来理解：

s1 = "abcde", s2 = "abfce"

构建DP表（多一行一列用于边界处理）：

    "" a  b  f  c  e
""   0  0  0  0  0  0
a    0  1  0  0  0  0  
b    0  0  2  0  0  0
c    0  0  0  0  1  0
d    0  0  0  0  0  0
e    0  0  0  0  0  1

详细填充过程：

1. 第一行第一列都是0（空字符串情况）

2. 比较s1[0]='a'和s2[0]='a'：

   • 字符相同，dp[1][1] = dp[0][0] + 1 = 1

3. 比较s1[0]='a'和s2[1]='b'：

   • 字符不同，dp[1][2] = 0

4. 比较s1[1]='b'和s2[1]='b'：

   • 字符相同，dp[2][2] = dp[1][1] + 1 = 1 + 1 = 2

5. 比较s1[2]='c'和s2[3]='c'：

   • 字符相同，dp[3][4] = dp[2][3] + 1 = 0 + 1 = 1

6. 比较s1[4]='e'和s2[4]='e'：

   • 字符相同，dp[5][5] = dp[4][4] + 1 = 0 + 1 = 1

步骤5：记录结果
在填充DP表的过程中，我们需要记录：

• 最大长度max_len
• 结束位置end_pos

从表中可以看出：

• 最大值为2，出现在dp[2][2]
• 对应子串为"ab"

代码实现

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    # 创建DP表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    max_len = 0  # 记录最长公共子串长度
    end_pos = 0  # 记录在s1中的结束位置
    
    # 填充DP表
    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
    
    # 提取最长公共子串
    if max_len == 0:
        return ""
    else:
        return s1[end_pos - max_len:end_pos]

# 测试
s1 = "abcde"
s2 = "abfce"
result = longest_common_substring(s1, s2)
print(f"最长公共子串: '{result}'")  # 输出: 'ab' 或 'ce'

空间优化

由于我们只需要前一行的信息，可以将空间复杂度从O(m×n)优化到O(n)：

def longest_common_substring_optimized(s1, s2):
    m, n = len(s1), len(s2)
    # 只保存前一行的DP值
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    max_len = 0
    end_pos = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
                if curr[j] > max_len:
                    max_len = curr[j]
                    end_pos = i
            else:
                curr[j] = 0
        # 交换当前行和前一行的引用
        prev, curr = curr, prev
        # 重置当前行（可选，因为下次会被覆盖）
        for k in range(n + 1):
            curr[k] = 0
    
    if max_len == 0:
        return ""
    else:
        return s1[end_pos - max_len:end_pos]

复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度
• 空间复杂度：基础版本O(m×n)，优化版本O(n)

关键点总结

1. 状态定义：dp[i][j]表示以s1[i-1]和s2[j-1]结尾的公共子串长度
2. 连续性要求：字符不匹配时直接置0，因为子串必须连续
3. 结果提取：需要记录最大长度和结束位置来重构子串
4. 空间优化：利用滚动数组思想减少空间使用

这个算法很好地体现了动态规划在字符串匹配问题中的应用，通过子问题的解来构建原问题的解。