Knuth–Morris–Pratt，简称 KMP，是一种经典的字符串模式匹配算法，用于在 Text 中寻找一个 Pattern。
KMP 最重要的思想是：发生 mismatch 时，不需要丢弃之前已经获得的全部匹配信息。
为此，它会先对 Pattern 进行预处理，构造一个叫做 LPS 的数组。
什么是 LPS？
LPS 是：
Longest Proper Prefix which is also a Suffix
的缩写。
它记录当前 Pattern 子串中，既是 Proper Prefix 又是 Suffix 的最长字符串长度。
例如：
Pattern: A B A B A C
LPS: 0 0 1 2 3 0
对于 ABAB，AB 同时是 Prefix 和 Suffix，因此 LPS 值为 2。
为什么需要 LPS？
假设已经成功匹配了 j 个字符，然后发生 mismatch。
Naive Search 可能重新从 Pattern 开头开始，而 KMP 使用：
j = lps[j - 1]
这样可以保留之前 Match 中仍然有用的信息。
TypeScript 构建 LPS
function buildLPS(pattern: string): number[] {
const lps = new Array(pattern.length).fill(0);
let length = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
i++;
} else if (length !== 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
return lps;
}
对于：
ABABCABAB
LPS 为：
[0, 0, 1, 2, 0, 1, 2, 3, 4]
KMP 搜索实现
function kmpSearch(text: string, pattern: string): number {
if (pattern.length === 0) return 0;
const lps = buildLPS(pattern);
let i = 0;
let j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) {
return i - j;
}
} else if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
其中 i 表示 Text 的位置，j 表示 Pattern 的位置。
KMP 的一个关键特点是：Text 指针 i 不会向后移动。
时间复杂度
如果 Text 长度是 n，Pattern 长度是 m：
构建 LPS: O(m)
搜索: O(n)
总计: O(n + m)
空间: O(m)
而 Naive Search 的最坏情况可能达到：
O(n × m)
为什么 KMP 更高效？
考虑：
Text:
AAAAAAAAAAAAAAAAAB
Pattern:
AAAAAB
Naive Search 可能反复比较大量相同的 A。
KMP 通过 LPS 了解 Pattern 自身的重复结构，因此能够减少这些重复比较。
实际应用
KMP 和相关的 String Matching 技术可以用于：
- 文本搜索
- Log 分析
- DNA Sequence 搜索
- 数据流模式匹配
- 安全 Signature 检测
- 算法和技术面试题
技术面试中的 KMP
相关问题可能包括：
- Find substring
- Find all occurrences
- Build LPS array
- Longest prefix that is also suffix
- Repeated substring pattern
重点不是死记代码，而是理解 LPS 如何保存之前 Match 的信息。
常见实现错误
当 mismatch 发生且 j > 0 时，不应该同时增加 i。
只需要：
j = lps[j - 1]
因为当前 Text 字符仍需要与 Pattern 的新位置比较。
总结
KMP 是一种利用 Pattern 内部结构来避免重复比较的字符串搜索算法。
它首先构造 LPS 数组，然后在搜索阶段复用之前匹配得到的信息。
Time Complexity: O(n + m)
Space Complexity: O(m)
理解 KMP 最关键的一句话是：
mismatch 并不意味着之前成功 Match 的所有信息都应该被丢弃。
LPS 正是用来保存和利用这些信息的。