线性动态规划：最长公共子串（Longest Common Substring）

题目描述：给定两个字符串s1和s2，要求找到它们的最长公共子串。公共子串要求是连续的字符序列。例如s1 = "abcde", s2 = "abfce"，最长公共子串是"ab"或"ce"，长度为2。

解题过程：

1. 问题分析：

• 与最长公共子序列不同，子串要求连续
• 暴力解法需要O(n²)个子串起点和O(n)的比较时间，总复杂度O(n³)
• 使用动态规划可以优化到O(n²)

2. 动态规划定义：
   定义dp[i][j]表示以s1的第i个字符和s2的第j个字符结尾的最长公共子串的长度。

3. 状态转移方程：

• 如果s1[i-1] == s2[j-1]（注意字符串索引从0开始）：
  dp[i][j] = dp[i-1][j-1] + 1
• 如果s1[i-1] != s2[j-1]：
  dp[i][j] = 0

5. 边界条件：

• 当i=0或j=0时，dp[i][j] = 0（表示空字符串的情况）

6. 具体实现步骤：

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

7. 算法分析：

• 时间复杂度：O(m×n)，需要填充整个DP表
• 空间复杂度：O(m×n)，可以优化到O(min(m,n))

8. 空间优化：
   由于每次计算只用到上一行的数据，可以优化空间：

def longest_common_substring_optimized(s1, s2):
    if len(s1) < len(s2):
        s1, s2 = s2, s1  # 让s2是较短的字符串
    
    m, n = len(s1), len(s2)
    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  # 交换数组
    
    return s1[end_pos - max_len:end_pos] if max_len > 0 else ""

9. 关键理解点：

• dp[i][j]表示"以当前位置结尾"的公共子串长度
• 不匹配时要重置为0，因为连续性被打破
• 需要额外变量记录最大值和位置信息