KMP 算法全网最通透解析（附 P3375 AC 代码）

一、题目背景P3375 【模板】KMP这道题是洛谷模板题也是 KMP 算法的标准入门题。题目核心要求给定两个字符串s1文本串长度为 n和s2模式串长度为 m请完成两个任务匹配任务找出s2在s1中所有出现的位置位置从1开始计数。前缀函数任务输出模式串s2每个前缀的最长 Border 长度即 KMP 的Next数组。输入输出样例输入ABABABC ABA输出1 3 0 0 1二、为什么要用 KMP从暴力匹配说起如果你写暴力匹配双重循环时间复杂度是O(n×m)。当数据量达到 105 级别时暴力匹配直接TLE超时。暴力匹配的致命缺陷比如s1 AAAAABAAAAAs2 AAAAA当匹配到第 5 个字符时BvsA失配。暴力做法文本串指针 i 回退到1模式串指针 j 回退到0从头开始比。问题大量重复的比较操作被执行了浪费了宝贵的运行时间。KMP 的核心思想利用模式串本身的对称性在失配时不回退文本串指针 i只回退模式串指针 j。这使得时间复杂度降为O(nm)线性时间解决匹配问题。三、核心概念什么是 Next 数组KMP 的关键在于Next 数组也叫前缀函数。1. 定义对于字符串 s 的前缀 s[0...i]Next[i]表示该前缀的最长真 Border长度。2. 什么是 BorderBorder一个字符串的非空真子串满足既是前缀又是后缀。比如ABAB前缀AB既是前缀又是后缀 → 是 Border。前缀ABA不是 → 不等于后缀。所以ABAB的最长 Border 是AB长度为 2。3. Next 数组的作用当匹配失败时文本串 i 不动。模式串 j 直接跳转到Next[j-1]的位置。原因Next[j-1]记录了当前最长的公共前后缀我们只需要从这个位置继续匹配不用重复比较已经匹配过的字符。四、算法详解Next 数组 匹配过程1. Next 数组求解算法前缀函数时间复杂度O(m)核心逻辑初始化Next[0] 0单个字符没有真子串。对于 i 从 1 到 m−1令 jNext[i−1]继承前一位的最长公共前后缀长度。失配回溯只要 j0 且 s[i]s[j]就令 jNext[j−1]。匹配成功如果 s[i]s[j]则 j。令Next[i] j。代码实现vectorint get_next(const string s) { int m s.size(); vectorint Next(m, 0); // Next数组初始化 for (int i 1; i m; i) { int j Next[i - 1]; // 关键利用之前的信息 // 失配时不断回溯 while (j 0 s[i] ! s[j]) { j Next[j - 1]; } // 匹配成功长度加1 if (s[i] s[j]) { j; } Next[i] j; } return Next; }2. KMP 匹配过程时间复杂度O(n)核心逻辑定义双指针 i遍历文本串和 j遍历模式串。遍历文本串失配回溯如果 j0 且字符不相等令 jNext[j−1]。匹配成功如果字符相等令 j。完全匹配当 jm 时说明找到一个匹配位置。计算位置并记录然后令 jNext[j−1]为了寻找重叠匹配。代码实现vectorint kmp_match(const string s1, const string s2, const vectorint Next) { int n s1.size(), m s2.size(); vectorint res; // 存储匹配位置 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) { // 位置转换0-based 转 1-based res.push_back(i - m 2); // 继续寻找下一个匹配 j Next[j - 1]; } } return res; }五、完整 AC 代码包含了输入输出、Next 数组计算、KMP 匹配复制即可 AC。#include iostream #include vector #include string using namespace std; // 1. 计算Next数组前缀函数 vectorint get_next(const string s) { int m s.size(); vectorint Next(m, 0); for (int i 1; i m; i) { int j Next[i - 1]; while (j 0 s[i] ! s[j]) { j Next[j - 1]; } if (s[i] s[j]) { j; } Next[i] j; } return Next; } // 2. KMP匹配逻辑 vectorint kmp(const string s1, const string s2, const vectorint Next) { int n s1.size(), m s2.size(); vectorint pos; 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) { pos.push_back(i - m 2); // 转换为1-based下标 j Next[j - 1]; // 继续匹配下一个 } } return pos; } int main() { // 加速IO竞赛必备 ios::sync_with_stdio(false); cin.tie(nullptr); string s1, s2; cin s1 s2; vectorint Next get_next(s2); vectorint positions kmp(s1, s2, Next); // 输出所有匹配位置 for (int p : positions) { cout p \n; } // 输出Next数组题目要求 for (int i 0; i s2.size(); i) { cout Next[i] \n[i s2.size() - 1]; } return 0; }六、避坑指南新手必看数据类型溢出虽然 106 以内可以用 int但在竞赛中字符串长度和索引建议直接使用int。核心变量 i,j 必须是整型。位置转换题目要求从1开始输出位置。代码中i - m 2是 0-based 转 1-based 的关键公式。如果直接输出i - m 1会少 1导致 WA。Next 数组初始化Next[0]必须是 0不能留垃圾值。失配条件必须写while (j 0 ...)保证 j 不会越界变成 -1。七、总结KMP 算法是字符串匹配的基石。核心利用前缀函数Next 数组记录模式串的对称性。复杂度O(nm)秒杀暴力。适用场景所有单模式串匹配问题如查找关键词、统计出现次数、AC 自动机的基础。