假设你需要在一段百万字的文本中搜索一个关键词。最直观的方法是：将关键词与文本的每个位置逐一比较——时间复杂度 $O(nm)$，其中n是文本长度，m是关键词长度。当文本达到百万级别时，这个算法可能需要数秒甚至更长。
但如果告诉你，有一种方法能在 $O(n+m)$ 时间内完成同样的任务呢？这就是字符串匹配算法的魅力：通过预处理模式串，利用已匹配的信息避免重复比较，将二次复杂度降为线性复杂度。
在文本编辑器的查找功能、搜索引擎的索引构建、DNA序列比对、抄袭检测系统背后，字符串匹配算法都在默默工作。掌握KMP、Z函数、Rabin-Karp等核心算法，不仅能让你在面试中游刃有余，更能深刻理解计算机处理文本信息的底层逻辑。
朴素匹配：直观但低效的起点
在深入高效算法之前，先理解朴素匹配方法的问题所在。假设要在文本 haystack = "ABABABC" 中搜索模式 needle = "ABABC"：
朴素匹配从文本的第一个位置开始，逐字符比较。当匹配到第五个字符时发现不匹配（A vs C），于是将模式串向右移动一位，重新从头开始比较。问题在于：即使前四个字符已经匹配成功，我们仍然丢弃了这些信息，从零开始。
// 朴素匹配 - O(nm) 时间复杂度
public int strStrNaive(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) break;
}
if (j == m) return i;
}
return -1;
}
这种方法的致命缺陷在于：当不匹配发生时，已匹配的部分信息被完全浪费。高效算法的核心思想正是：如何利用这些已匹配信息，让模式串"聪明地"跳跃到下一个可能匹配的位置。
KMP算法：利用模式串自身的结构
1977年，Knuth、Morris、Pratt三人共同发表了线性时间字符串匹配算法。KMP算法的核心洞察是：当匹配失败时，模式串中已匹配的部分本身包含着关于"应该跳到哪个位置继续匹配"的信息。
前缀函数（LPS数组）的本质
考虑模式串 P = "ABABAC"。当我们在文本中匹配到第六个字符时发生失败，此时前五个字符 ABABA 已经匹配。观察这个已匹配部分：
- 前缀
AB等于后缀AB - 这意味着如果模式串向右移动三位，前两个字符
AB仍然能与文本匹配
这就是LPS（Longest Proper Prefix which is also Suffix）数组的核心思想：lps[i] 表示模式串 P[0...i] 的最长相等真前缀和真后缀的长度。“真"意味着不能是整个字符串本身。
以 P = "ABABAC" 为例：
lps[0] = 0：单个字符没有真前缀和真后缀lps[1] = 0："AB"没有相等的前后缀lps[2] = 1："ABA"的前缀"A"等于后缀"A"lps[3] = 2："ABAB"的前缀"AB"等于后缀"AB"lps[4] = 3："ABABA"的前缀"ABA"等于后缀"ABA"lps[5] = 0："ABABAC"没有相等的前后缀
图片来源: 阮一峰 - 字符串匹配的KMP算法
LPS数组的构建
构建LPS数组使用双指针技巧：len 指向当前最长匹配前缀的末尾，i 遍历模式串。
private int[] buildLPS(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0; // 当前最长匹配前后缀的长度
for (int i = 1; i < m; i++) {
// 不匹配时，回退到上一个可能的匹配位置
while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) {
len = lps[len - 1];
}
// 匹配时，扩展匹配长度
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
}
}
return lps;
}
为什么这能在线性时间内完成？关键在于 len 指针的行为：它要么增加（匹配时），要么减少（不匹配回退时）。由于 len 最多增加m次，总操作次数是 $O(m)$。
KMP匹配过程
有了LPS数组，匹配过程变得直观：当不匹配发生时，查询LPS数组决定模式串应该移动到哪个位置。
public int strStrKMP(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
int[] lps = buildLPS(needle);
int j = 0; // 模式串中的位置
for (int i = 0; i < n; i++) {
// 不匹配时，根据LPS数组跳转
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = lps[j - 1];
}
// 匹配时，推进模式串指针
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
// 完全匹配
if (j == m) {
return i - m + 1;
}
}
return -1;
}
时间复杂度分析：构建LPS数组 $O(m)$，匹配过程 $O(n)$，总计 $O(n+m)$。空间复杂度 $O(m)$ 用于存储LPS数组。
Z算法：更直观的线性匹配
Z算法提供了另一种线性时间的字符串匹配方法，其核心是Z函数。与KMP的前缀函数不同，Z函数关注的是"从每个位置开始，有多少字符与前缀匹配”。
Z函数的定义
对于字符串 S，Z[i] 定义为：从位置 i 开始的子串 S[i...] 与字符串前缀 S[0...] 的最长公共前缀长度。
例如 S = "aabxaab"：
Z[0]未定义（或视为0，因为整个字符串与自己的前缀比较没有意义）Z[1] = 1："abxaab"与"aabxaab"的最长公共前缀是"a"Z[4] = 3："aab"与"aabxaab"的最长公共前缀是"aab"
Z-box与线性构建
Z算法的精妙之处在于使用"Z-box"——一个区间 [l, r]，表示已知的与前缀匹配的最右边界。当处理位置 i 时：
- 如果
i > r：从头开始比较，计算新的Z值 - 如果
i <= r：利用已知信息，Z[i]至少是min(Z[i-l], r-i+1)
private int[] zFunction(String s) {
int n = s.length();
int[] z = new int[n];
int l = 0, r = 0; // Z-box边界
for (int i = 1; i < n; i++) {
// 利用已知信息
if (i <= r) {
z[i] = Math.min(r - i + 1, z[i - l]);
}
// 尝试扩展
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
z[i]++;
}
// 更新Z-box
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
用Z函数进行模式匹配
将模式串和文本拼接：pattern + "$" + text（$是不出现在两者中的分隔符）。计算Z数组后，任何 Z[i] == pattern.length 的位置 i 都对应一个匹配。
public List<Integer> strStrZ(String text, String pattern) {
String combined = pattern + "$" + text;
int[] z = zFunction(combined);
List<Integer> matches = new ArrayList<>();
int m = pattern.length();
for (int i = m + 1; i < combined.length(); i++) {
if (z[i] == m) {
matches.add(i - m - 1);
}
}
return matches;
}
Rabin-Karp：哈希加速的匹配
Rabin-Karp算法采用完全不同的思路：将字符串转换为数值，用数值比较代替字符比较。
滚动哈希的原理
将字符串视为一个进制数。对于字符串 "abc"，选择基数 d = 256，哈希值为：
关键是：当窗口向右滑动一位时，新哈希值可以通过旧哈希值快速计算：
$$h_{new} = (h_{old} - oldChar \times d^{m-1}) \times d + newChar$$public int strStrRabinKarp(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
if (m > n) return -1;
// 大质数用于取模，避免溢出
long MOD = 1_000_000_007L;
long base = 256L;
long baseM = 1; // base^m mod MOD
// 预计算 base^m
for (int i = 0; i < m; i++) baseM = (baseM * base) % MOD;
// 计算模式串和文本第一个窗口的哈希
long needleHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
needleHash = (needleHash * base + needle.charAt(i)) % MOD;
windowHash = (windowHash * base + haystack.charAt(i)) % MOD;
}
for (int i = 0; i <= n - m; i++) {
// 哈希匹配时，进行实际比较（避免哈希碰撞）
if (needleHash == windowHash) {
if (haystack.substring(i, i + m).equals(needle)) {
return i;
}
}
// 滚动计算下一个窗口的哈希
if (i < n - m) {
windowHash = (windowHash * base - haystack.charAt(i) * baseM % MOD + MOD) % MOD;
windowHash = (windowHash + haystack.charAt(i + m)) % MOD;
}
}
return -1;
}
Rabin-Karp特别适合多模式匹配：预处理所有模式串的哈希，然后在一次文本扫描中查找所有模式。
LeetCode实战：从理论到代码
LeetCode 28. Find the Index of the First Occurrence in a String
这是最基础的字符串匹配问题，KMP是最优解。
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
int[] lps = buildLPS(needle);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = lps[j - 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
private int[] buildLPS(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
for (int i = 1; i < m; i++) {
while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) {
len = lps[len - 1];
}
if (pattern.charAt(i) == pattern.charAt(len)) {
lps[i] = ++len;
}
}
return lps;
}
}
复杂度：时间 $O(n+m)$，空间 $O(m)$。
LeetCode 459. Repeated Substring Pattern
判断字符串是否由某个子串重复构成。一个巧妙的解法：将字符串翻倍后去掉首尾，如果原串仍能找到，说明存在重复模式。
class Solution {
public boolean repeatedSubstringPattern(String s) {
String doubled = (s + s).substring(1, s.length() * 2 - 1);
return doubled.contains(s);
}
}
也可以使用KMP的LPS数组：如果 lps[n-1] > 0 且 n % (n - lps[n-1]) == 0，则存在重复模式。
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
int[] lps = new int[n];
int len = 0;
for (int i = 1; i < n; i++) {
while (len > 0 && s.charAt(i) != s.charAt(len)) {
len = lps[len - 1];
}
if (s.charAt(i) == s.charAt(len)) {
lps[i] = ++len;
}
}
int lastLPS = lps[n - 1];
return lastLPS > 0 && n % (n - lastLPS) == 0;
}
}
原理：lps[n-1] 表示整个字符串的最长相等前后缀长度。如果这个长度能整除字符串长度，说明字符串可以由长度为 n - lps[n-1] 的子串重复构成。
LeetCode 1392. Longest Happy Prefix
寻找最长的"快乐前缀"——既是前缀又是后缀的最长子串。这正是LPS数组最后元素的含义。
class Solution {
public String longestPrefix(String s) {
int n = s.length();
int[] lps = new int[n];
int len = 0;
for (int i = 1; i < n; i++) {
while (len > 0 && s.charAt(i) != s.charAt(len)) {
len = lps[len - 1];
}
if (s.charAt(i) == s.charAt(len)) {
lps[i] = ++len;
}
}
return s.substring(0, lps[n - 1]);
}
}
复杂度：时间 $O(n)$，空间 $O(n)$。
LeetCode 214. Shortest Palindrome
通过在字符串前面添加字符，使其成为最短回文。核心是找到最长回文前缀。
KMP解法：将原串和其逆序拼接，计算LPS数组。
class Solution {
public String shortestPalindrome(String s) {
String rev = new StringBuilder(s).reverse().toString();
String combined = s + "#" + rev;
int[] lps = new int[combined.length()];
int len = 0;
for (int i = 1; i < combined.length(); i++) {
while (len > 0 && combined.charAt(i) != combined.charAt(len)) {
len = lps[len - 1];
}
if (combined.charAt(i) == combined.charAt(len)) {
lps[i] = ++len;
}
}
int longestPalinPrefix = lps[combined.length() - 1];
String toAdd = new StringBuilder(s.substring(longestPalinPrefix)).reverse().toString();
return toAdd + s;
}
}
原理：s + "#" + rev 的LPS数组最后元素，给出了原串与逆序串的最长公共前缀长度，这正是最长回文前缀的长度。
算法选择指南
| 算法 | 预处理时间 | 匹配时间 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 朴素匹配 | $O(1)$ | $O(nm)$ | $O(1)$ | 模式串极短时 |
| KMP | $O(m)$ | $O(n)$ | $O(m)$ | 通用字符串匹配 |
| Z算法 | $O(m)$ | $O(n)$ | $O(m)$ | 需要所有匹配位置时 |
| Rabin-Karp | $O(m)$ | $O(n)$ 平均 | $O(1)$ | 多模式匹配、扩展性好 |
| Boyer-Moore | $O(m+k)$ | $O(n/m)$ 最优 | $O(k)$ | 字符集较大时 |
其中 $k$ 是字符集大小。
现实应用
字符串匹配算法远不止是面试题：
文本编辑器 的查找功能需要实时响应，KMP或Boyer-Moore确保毫秒级响应。
DNA序列分析 中，人类基因组约30亿碱基对，需要在其中定位特定基因序列。高效的字符串匹配是生物信息学的基础工具。
搜索引擎 的倒排索引构建过程中，需要从海量文档中提取词项，字符串匹配是核心操作。
抄袭检测系统 通过比较文档间的相似片段来识别抄袭，本质上是多模式字符串匹配问题。
算法演进的启示
从朴素匹配的 $O(nm)$ 到KMP的 $O(n+m)$，字符串匹配算法的演进揭示了计算机科学的一个深刻道理：预处理换取运行时效率。通过预先分析模式串的结构（LPS数组、Z数组），我们在匹配阶段能够做出更明智的决策。
更重要的是，KMP算法教会我们一个通用的问题解决策略：不要浪费已获得的信息。当匹配失败时，已匹配的部分不是毫无价值的废料，而是蕴含着"下一步该怎么做"的线索。这种"信息复用"的思想，在动态规划、后缀自动机等更复杂的算法中都有体现。
参考文献：
- Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350.
- Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762-772.
- Karp, R. M., & Rabin, M. O. (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2), 249-260.