KMP
高级KMP 的 next 数组让匹配失败时不需要回溯主串指针。
// 算法讲解
KMP
将输入字符串当作模式串，自动用部分重复文本演示 KMP 匹配。
待机
速度 中
待机 ⌨1vector<int> buildNext(const string& pat) {
2 int m = pat.size();
3 vector<int> nxt(m, 0);
4 for (int i = 1, j = 0; i < m; i++) {
5 while (j > 0 && pat[i] != pat[j]) j = nxt[j - 1];
6 if (pat[i] == pat[j]) j++;
7 nxt[i] = j;
8 }
9 return nxt;
10}
11
12int kmpSearch(const string& txt, const string& pat) {
13 auto nxt = buildNext(pat);
14 for (int i = 0, j = 0; i < (int)txt.size(); i++) {
15 while (j > 0 && txt[i] != pat[j]) j = nxt[j - 1];
16 if (txt[i] == pat[j]) j++;
17 if (j == (int)pat.size()) return i - j + 1;
18 }
19 return -1;
20}
复杂度分析
时间 O(n + m)
空间 O(m)
最优 O(n)
最坏 O(n + m)
算法讲解
KMP 算法在匹配失败时不回退主串指针，而是利用已匹配部分的信息跳过不可能匹配的位置。
关键是预处理模式串的 next 数组（部分匹配表），next[i] 表示 pattern[0..i] 的最长相等前后缀长度。
匹配失败时根据 next 数组决定模式串右移多少位，保证不遗漏也不重复。
时间复杂度 O(n+m)，是字符串匹配的理论最优。