在一段长文本里找一个模式串出现的所有位置——失配时不用从头重新比较，靠模式串自己的"前后缀信息"跳过注定失败的尝试。
在文本串 s（长度 n）里查找模式串 p（长度 m）出现的位置，最直接的办法是：从文本的每一个位置开始，逐字符和模式串比较，一旦某个位置失配，就挪到下一个起始位置重新从头比较。这种朴素做法最坏情况下要比较 O(n×m) 次——如果文本和模式串都很长，会非常慢。
朴素做法慢在哪？失配之后把已经比较过的信息全部扔掉，重新从模式串的第一个字符开始比较——但其实已经匹配的这一段字符里，往往藏着有用的信息："模式串自己的某一段前缀，恰好和已经匹配上的这段文本的某个后缀相同"，可以利用这一点，直接跳到一个更靠后、不会白费功夫的位置继续比较。KMP 算法（Knuth-Morris-Pratt）就是把这份信息预先算好，失配时查表就知道该跳到哪。
KMP 的核心是给模式串 p 预处理一个 next 数组（也叫失配函数）：next[i] 表示 p[1..i] 这一段前缀里，最长的、同时也是后缀的"真前缀"长度（"真"指不能是整个 p[1..i] 自身）。这个信息只和模式串本身有关，和文本串无关，可以提前一次性算好。
以模式串 p = "abab"（m=4）为例：
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 前缀 p[1..i] | a | ab | aba | abab |
| next[i] | 0 | 0 | 1 | 2 |
next[3]=1：前缀 "aba" 里，真前缀有 "a"、"ab"，真后缀有 "a"、"ba"，最长的共同部分是 "a"（长度 1）。next[4]=2：前缀 "abab" 里，真前缀 "aba" 和真后缀 "bab" 不同，但真前缀 "ab" 和真后缀 "ab" 相同（长度 2），这是能找到的最长匹配。在文本串 s = "ababdabab"（n=9）里查找模式串 p = "abab" 出现的所有位置。i 是文本指针，j 是模式串指针，两者都从 1 开始，s[i] 和 p[j] 相等就同时前进；失配时，如果 j>1，就跳到 j = next[j-1] + 1 继续比较（不移动 i）；如果 j=1 还失配，只能移动 i：
| i | j | s[i] | p[j] | 结果 | 下一步 |
|---|---|---|---|---|---|
| 1 | 1 | a | a | 匹配 | i=2, j=2 |
| 2 | 2 | b | b | 匹配 | i=3, j=3 |
| 3 | 3 | a | a | 匹配 | i=4, j=4 |
| 4 | 4 | b | b | 匹配 | j 达到 m=4 |
| j 达到模式串长度 4 —— 在位置 i-m+1 = 1 处找到一次匹配！继续查找：j = next[4] = 2（不回退 i） | |||||
| 5 | 2 | d | b | 失配 | j>1，跳到 j = next[1]+1 = 1 |
| 5 | 1 | d | a | 失配 | j=1，移动 i：i=6 |
| 6 | 1 | a | a | 匹配 | i=7, j=2 |
| 7 | 2 | b | b | 匹配 | i=8, j=3 |
| 8 | 3 | a | a | 匹配 | i=9, j=4 |
| 9 | 4 | b | b | 匹配 | j 达到 m=4 |
| j 再次达到 4 —— 在位置 i-m+1 = 6 处找到第二次匹配！ | |||||
i 只从 1 单调增加到 9，一次都没有回退——真正回退、重新比较的只有指针 j，而且 j 的回退是靠查 next 表直接跳到位，不需要逐个尝试。最终在文本的第 1 位和第 6 位各找到一次 "abab"。next[j-1]+1"是安全的？失配发生在 j 位置，说明 s 里已经匹配上的这一段，恰好等于模式串的前缀 p[1..j-1]。next[j-1] 告诉我们：p[1..j-1] 这段前缀本身，又恰好在结尾处重复了长度为 next[j-1] 的一段（既是前缀也是后缀）。也就是说，已经匹配上的文本末尾那一小段，天然就和模式串新的前缀 p[1..next[j-1]] 对得上，不需要再重新验证，直接从 p[next[j-1]+1] 继续比较就行，这正是省下重复比较的关键。| 1 | int nxt[MAXM]; // nxt[i]：p[1..i] 的最长相同真前后缀长度 |
| 2 | |
| 3 | void BuildNext(const string& p) // p 下标从 0 开始，p[i-1] 对应第 i 个字符 |
| 4 | { |
| 5 | int m = p.size(); |
| 6 | nxt[1] = 0; |
| 7 | int j = 0; // j：当前已经匹配上的前后缀长度 |
| 8 | for (int i = 2; i <= m; i++) |
| 9 | { |
| 10 | while (j > 0 && p[i-1] != p[j]) // ★ 失配就用 next 数组回退 j（自己给自己做 KMP） |
| 11 | j = nxt[j]; |
| 12 | if (p[i-1] == p[j]) j++; |
| 13 | nxt[i] = j; |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | void KmpSearch(const string& s, const string& p) |
| 18 | { |
| 19 | int n = s.size(), m = p.size(); |
| 20 | BuildNext(p); |
| 21 | int j = 0; // j：模式串已经匹配到第几位 |
| 22 | for (int i = 1; i <= n; i++) |
| 23 | { |
| 24 | while (j > 0 && s[i-1] != p[j]) // ★ 失配，查 next 表跳转 j，i 不动 |
| 25 | j = nxt[j]; |
| 26 | if (s[i-1] == p[j]) j++; |
| 27 | if (j == m) // j 达到模式串长度，说明匹配上了一次 |
| 28 | { |
| 29 | cout << "匹配位置：" << i - m + 1 << endl; |
| 30 | j = nxt[j]; // 继续查找下一次匹配，不重置为 0 |
| 31 | } |
| 32 | } |
| 33 | } |
next 数组的代码，本质是"用 KMP 匹配自己"：第 10～13 行的结构，和第 24～26 行匹配文本串的结构几乎一模一样——因为构建 next 数组，就是在拿模式串的每个前缀去匹配模式串自己。理解了下面 KmpSearch 的匹配逻辑，回头看 BuildNext 会发现它们是同一套代码的两种应用。next 数组的下标定义（是否从 0 开始、next[i] 到底对应"前 i 个字符"还是"前 i-1 个字符"）存在多种写法，直接照抄网上代码片段容易和自己使用的约定对不上。写代码前先明确自己用的是哪一种定义，前后保持一致。j = nxt[j] 而不是直接 j = 0——重置为 0 虽然也能继续找到后续的匹配，但会丢弃"当前已匹配的这一段末尾，可能也是模式串前缀的一部分"这个信息，导致某些重叠的匹配被漏掉（比如模式串本身首尾有重复结构、多次匹配相互重叠的情况）。i 全程只增不减"，回退的只有模式串指针 j。如果实现中不小心让 i 也发生回退（比如照搬朴素匹配的框架又混入了 next 跳转），会失去 KMP O(n+m) 的复杂度保证，退化成接近朴素匹配的效率。