线性动态规划：最长公共子序列的变种——最长公共子串（Longest Common Substring） 题目描述 给定两个字符串 s1 和 s2 ，要求找到它们的最长公共子串。公共子串是指两个字符串中连续相同的字符序列。例如，对于 s1 = "abcde" 和 s2 = "abfce" ，最长公共子串是 "ab" 或 "c" （长度为2或1，但最长长度为2）。 解题思路 与最长公共子序列（LCS）不同，公共子串要求字符必须是连续的。我们可以使用动态规划来解决这个问题，通过记录以每个字符结尾的公共子串长度来避免重复计算。 详细步骤 步骤1：定义状态 定义 dp[i][j] 表示以 s1 的第 i 个字符和 s2 的第 j 个字符结尾的最长公共子串的长度。注意，这里的下标从1开始计数，实际编程时可能需要调整索引。 步骤2：状态转移方程 如果 s1[i-1] == s2[j-1] （因为字符串索引从0开始），说明当前字符可以延长公共子串，因此： 如果 s1[i-1] != s2[j-1] ，则以这两个字符结尾的公共子串长度为0： 步骤3：初始化 当 i = 0 或 j = 0 时，表示一个字符串为空，公共子串长度为0： 步骤4：记录最大值 在填充 dp 表的过程中，记录遇到的最大值 max_len ，并同时记录该子串的结束位置，以便后续还原子串。 步骤5：复杂度分析 时间复杂度：O(n* m)，其中 n 和 m 分别是 s1 和 s2 的长度。 空间复杂度：可优化至 O(min(n, m))，通过滚动数组技术。 示例演示 以 s1 = "abcde" , s2 = "abfce" 为例： 初始化 dp 表大小为 (6, 6) （包含空串情况）。 逐行填充： 当 i=1, j=1 ： s1[0]='a' == s2[0]='a' ， dp[1][1] = dp[0][0] + 1 = 1 当 i=2, j=2 ： s1[1]='b' == s2[1]='b' ， dp[2][2] = dp[1][1] + 1 = 2 当 i=3, j=3 ： s1[2]='c' != s2[2]='f' ， dp[3][3] = 0 继续填充，发现 dp[4][4] = 1 （对应字符 'c' ）和 dp[5][5] = 1 （对应字符 'e' ）。 最大值 max_len = 2 ，对应子串 "ab" 。 优化与扩展 空间优化 ：使用一维数组 dp 和临时变量保存上一行的值，将空间复杂度降至 O(m)。 输出子串 ：通过记录最大值时的索引 i ，可以从 s1 中截取子串 s1[i-max_len : i] 。 多解情况 ：若需所有最长公共子串，可遍历 dp 表收集所有等于 max_len 的位置。 通过以上步骤，即可高效求解最长公共子串问题。