最长公共子串 题目描述： 给定两个字符串 s1 和 s2 ，要求找出它们最长的公共子串。公共子串是指连续出现在两个字符串中的相同字符序列。例如， s1 = "abcde" ， s2 = "abfce" ，最长公共子串是 "ab" 或 "bc" （长度为 2）。注意子串是连续的，而子序列可以不连续。 解题过程 1. 问题分析 与最长公共子序列（LCS）不同，公共子串要求字符连续出现，因此状态定义需体现连续性。 暴力解法：枚举 s1 的所有子串，检查是否在 s2 中出现，时间复杂度 O(n²·m)，效率低。 动态规划思路：通过记录以每个位置结尾的公共子串长度，避免重复计算。 2. 状态定义 定义 dp[i][j] ：表示以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串的长度。 （注：索引从 0 开始，但 dp 表通常用 i=0 或 j=0 表示空串，方便初始化。） 3. 状态转移方程 若 s1[i-1] == s2[j-1] ：说明当前字符可延长公共子串，故 dp[i][j] = dp[i-1][j-1] + 1 。 若 s1[i-1] != s2[j-1] ：连续性被破坏，以这两个字符结尾的公共子串长度为 0，即 dp[i][j] = 0 。 4. 初始化 当 i=0 或 j=0 时，表示一个字符串为空，公共子串长度为 0，即 dp[0][j] = 0 ， dp[i][0] = 0 。 5. 计算与记录结果 遍历 i 从 1 到 len(s1) ， j 从 1 到 len(s2) ，填充 dp 表。 同时记录遍历过程中的最大 dp[i][j] 及其位置，即可得到最长公共子串的长度和结束位置。 6. 示例演示 以 s1 = "abcde" ， s2 = "abfce" 为例（简化表格，省略空串行/列）： | | "" | 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 | 最大值为 2（对应子串 "ab" 或 "bc"），长度为 2。 7. 复杂度分析 时间复杂度：O(n·m)，n、m 为两字符串长度。 空间复杂度：可优化至 O(min(n, m))，仅需保留上一行 dp 值。