最长公共子串 （Longest Common Substring） 题目描述： 给定两个字符串 text1 和 text2 ，要求返回这两个字符串的最长公共子串的长度。 注意：子串要求连续，不同于子序列（可以不连续）。例如， "abcde" 和 "abfce" 的公共子串是 "ab" 和 "c" ，最长公共子串长度为 2（"ab"）。 解题思路 1. 暴力解法（直接枚举） 枚举字符串 text1 的所有子串，检查是否在 text2 中出现，并记录最大长度。 时间复杂度：O(n²) 个子串，每个子串在 text2 中匹配需要 O(m)，总复杂度 O(n² * m)，效率低。 2. 动态规划（DP）思路 我们定义 dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串的长度。 如果 text1[i-1] == text2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。 如果不等，则 dp[i][j] = 0 （因为子串必须连续，一旦不匹配就要重新计数）。 最终答案是所有 dp[i][j] 中的最大值。 3. 详细步骤 初始化一个二维数组 dp ，大小为 (len(text1)+1) x (len(text2)+1) ，初始值为 0。 遍历 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 = max(max_len, dp[i][j]) 返回 max_len 。 4. 示例演示 以 text1 = "abcde" , text2 = "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"）。 5. 优化空间复杂度 因为 dp[i][j] 只依赖于 dp[i-1][j-1] ，可以只保留上一行和当前行，空间复杂度从 O(n* m) 降到 O(min(n, m))。 如果你理解了，我可以再给你讲一个相关的变种题目（比如最长公共子序列，或者带输出具体子串的版本）。