Longest Common Substring 问题要求找出两个字符串中最长的连续公共字符序列。
例如：
ABABC
BABCA
最长的公共连续部分是：
BABC
因此：
Length = 4
Substring 必须连续
对于：
ABCDE
以下都是 Substring：
ABC
BCD
DE
但是 ACE 不是，因为字符并不连续。
动态规划定义
定义：
dp[i][j]
表示恰好在 a[i - 1] 和 b[j - 1] 位置结束的最长公共子串长度。
如果当前字符相同：
dp[i][j] = dp[i - 1][j - 1] + 1
如果不同：
dp[i][j] = 0
之所以重置为 0，是因为 Substring 必须连续，任何 mismatch 都会打断当前匹配链。
示例 DP 表
对于：
a = ABABC
b = BABCA
可以得到：
B A B C A
A 0 1 0 0 1
B 1 0 2 0 0
A 0 2 0 0 1
B 1 0 3 0 0
C 0 0 0 4 0
最大值为 4，对应 BABC。
TypeScript 实现
function longestCommonSubstring(
a: string,
b: string
): string {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i;
}
}
}
}
return a.slice(endIndex - maxLength, endIndex);
}
复杂度
如果两个字符串长度分别是 n 和 m：
Time Complexity: O(n × m)
Space Complexity: O(n × m)
由于当前行只依赖上一行，可以把空间优化到：
O(min(n, m))
与 Longest Common Subsequence 的区别
Substring 要求字符连续。
Subsequence 只要求顺序保持一致。
例如：
ABCDEF
ACEF
ACEF 可以是 Common Subsequence，但并不是第一个字符串中的连续 Substring。
动态规划中最明显的区别是：
Longest Common Substring mismatch → 0
而 LCS 在 mismatch 时通常会从相邻状态中选择较大值。
实际应用
Longest Common Substring 可用于：
- 字符串相似度
- CRM 数据去重
- Data Cleaning
- DNA Sequence 分析
- 文档比较
- 版本比较
- Log Pattern 分析
例如在 CRM 数据清洗中，较长的公共字符串可以成为两个记录可能相关的一个 Signal，但生产环境还应该结合 Email、Phone、Levenshtein Distance 和 Token Similarity 等信息。
多个最优答案
可能存在多个相同最大长度的公共 Substring。
例如：
abcXYZ123
abcABC123
abc 和 123 的长度都为 3。
技术面试重点
需要理解：
- Substring 必须连续。
dp[i][j]的含义。- mismatch 时为什么重置为 0。
- 为什么要单独维护最大值。
- 时间复杂度为
O(n × m)。
总结
Longest Common Substring 的核心状态转移非常直接：
Match → dp[i - 1][j - 1] + 1
Mismatch → 0
这也是它与 Longest Common Subsequence 最重要的区别。