【数据结构与算法】KMP算法（next数组）

#include iostream #include string #include vector using namespace std; int main() { string s1, s2; cin s1 s2; int n s1.size(); int m s2.size(); // Step 1: 构建 next 数组 (border 长度数组) vectorint next(m, 0); for (int i 1; i m; i) { int j next[i - 1]; while (j 0 s2[i] ! s2[j]) { j next[j - 1]; } if (s2[i] s2[j]) { j; } next[i] j; } // Step 2: KMP 匹配记录位置 vectorint positions; int j 0; for (int i 0; i n; i) { while (j 0 s1[i] ! s2[j]) { j next[j - 1]; } if (s1[i] s2[j]) { j; } if (j m) { // 匹配成功位置是 i - m 1 (0-based) positions.push_back(i - m 2); // 转为 1-based j next[j - 1]; } } // Step 3: 输出匹配位置 for (int i 0; i positions.size(); i) { cout positions[i] \n; } // Step 4: 输出 border 长度 (即 next 数组) for (int i 0; i m; i) { cout next[i]; if (i m - 1) cout ; } return 0; }KMP算法入门到实战从原理到洛谷P3375完整解析字符串匹配是数据结构与算法中非常经典的一类问题。最朴素的方法是暴力匹配但在数据规模较大的情况下效率很低而KMP算法正是为了解决这一问题而提出的。这篇文章结合洛谷 P3375 这道模板题从原理到代码完整讲清楚 KMP 到底在干什么以及为什么它能做到高效匹配。问题背景字符串匹配到底在做什么给定两个字符串主串 s1模式串 s2我们需要找到s2 在 s1 中所有出现的位置。例如s1 ABABABC s2 ABA答案是1 3也就是 s2 在 s1 中出现了两次。暴力匹配的问题为什么需要KMP最直接的想法是从 s1 的每个位置开始一个字符一个字符去比但问题在于一旦匹配失败我们就会“回退很多无意义的比较”例如ABABABC ABA匹配到一半失败又要从头开始很多字符被重复比较。KMP 的核心思想就是不回退主串利用已经匹配的信息直接跳到合理的位置继续匹配KMP核心next数组border思想KMP最关键的就是next数组也叫前缀函数。它的含义是next[i] 表示子串 s2[0...i] 的最长“前缀 后缀”的长度这里的“前缀”和“后缀”前缀从开头开始的子串后缀从结尾开始的子串但不能是整个字符串本身例如s2 ABA计算过程A → 0AB → 0ABA → 1前缀A 后缀A所以next [0, 0, 1]为什么next数组这么重要当匹配失败时我们可以利用 next 数组把模式串往右“滑动”但不是重新开始而是跳到一个已经匹配过的位置本质上就是已经匹配成功的一部分不需要重新匹配直接复用这就是 KMP 能做到 O(n m) 的原因。代码解析一步一步看懂实现next数组构建过程别只背模板这一段是很多人卡住的地方for (int i 1; i m; i) { int j next[i - 1]; while (j 0 s2[i] ! s2[j]) { j next[j - 1]; } if (s2[i] s2[j]) { j; } next[i] j; }可以这样理解j 表示“当前能匹配的前缀长度”如果失配就往更短的 border 跳直到找到可以继续匹配的位置本质是在“历史信息”中找一个还能继续匹配的位置匹配过程真正体现KMP价值的地方这一段逻辑和 next 构建几乎一样while (j 0 s1[i] ! s2[j]) { j next[j - 1]; }含义是如果当前字符不匹配就利用 next 数组“跳回去”而不是从头开始当j m时说明完整匹配了一次记录位置然后继续匹配支持重叠本题额外要求border长度输出题目不仅要求匹配位置还要求输出 s2 每个前缀的最长 border 长度其实就是next 数组本身所以直接输出即可。一个容易忽略的细节这一句positions.push_back(i - m 2);很多人会写错。原因是i 是当前匹配结束位置0-based起点 i - m 1再转成 1-based → 1所以是i - m 2总结KMP其实可以用一句话概括利用“已经匹配过的信息”避免重复比较核心只有两个next数组记录可复用信息匹配时不回退主串理解了这一点代码只是形式。最后一点建议如果你觉得KMP难大概率不是代码问题而是没真正理解“next数组在表示什么”建议你自己拿一个字符串比如ABABAC手动推一遍 next 数组你会突然明白很多。一旦这一步通了KMP基本就彻底掌握了。