【板子】kmp

#include iostream #include string #include vector using namespace std; // 求模式串p的next数组最长border vectorint getNext(const string p) { int n p.size(); vectorint next(n 1, 0); // next[1]~next[n] 对应长度1~n前缀 int j 0; for (int i 2; i n; i) { while (j 0 p[i - 1] ! p[j]) j next[j]; if (p[i - 1] p[j]) j; next[i] j; } return next; } // KMP匹配返回所有匹配起始位置1开头 vectorint kmpSearch(const string s, const string p, const vectorint next) { vectorint res; int n s.size(), m p.size(); int j 0; for (int i 1; i n; i) { while (j 0 s[i - 1] ! p[j]) j next[j]; if (s[i - 1] p[j]) j; // 完全匹配 if (j m) { res.push_back(i - m 1); // 左端点l1起始 j next[j]; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s1, s2; cin s1 s2; auto next getNext(s2); auto pos kmpSearch(s1, s2, next); // 输出所有匹配位置 for (int x : pos) cout x \n; // 输出next[1]~next[m]空格分隔 int m s2.size(); for (int i 1; i m; i) { cout next[i] ; } return 0; }next特性len-next[len]是最小循环节优化失配数组#include iostream #include string #include vector using namespace std; vectorint getNext(const string p) { int n p.size(); vectorint next(n 1, 0); int j 0; for (int i 2; i n; i) { while (j 0 p[i - 1] ! p[j]) j next[j]; if (p[i - 1] p[j]) j; next[i] j; } return next; } // 生成nextval优化数组 vectorint getNextVal(const string p, const vectorint next) { int n p.size(); vectorint nextval(n 1, 0); nextval[1] 0; for (int i 2; i n; i) { int k next[i]; while (k 0 p[i - 1] p[k]) k next[k]; nextval[i] k; } return nextval; } // KMP匹配改用nextval vectorint kmpSearchVal(const string s, const string p, const vectorint nextval) { vectorint res; int n s.size(), m p.size(); int j 0; for (int i 1; i n; i) { while (j 0 s[i - 1] ! p[j]) j nextval[j]; if (s[i - 1] p[j]) j; if (j m) { res.push_back(i - m 1); j nextval[j]; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s1, s2; cin s1 s2; auto next getNext(s2); auto nextval getNextVal(s2, next); auto pos kmpSearchVal(s1, s2, nextval); for (int x : pos) cout x \n; int m s2.size(); for (int i 1; i m; i) cout nextval[i] ; return 0; }KMP 完整原理分三层讲问题、暴力缺陷、next 数组、匹配流程、nextval 优化一、原始问题字符串模式匹配给定文本串 S长 n、模式串 P长 m找出 S 中所有 P 出现的位置。暴力匹配缺点两个指针 i文本、j模式匹配相等\(i,j\)失配i 回退到 \(i-j2\)j 归零 最坏复杂度 \(O(nm)\)如SaaaaaaaPaaab大量重复比较浪费时间。KMP 核心目标失配时文本指针 i 不回退只让模式指针 j 跳到最优位置整体线性 \(O(nm)\)。二、核心概念Border前缀函数 /next 数组1. 定义对模式串前 i 个字符组成的前缀 \(P[1,i]\)真前缀不包含最后一位真后缀不包含第一位\(next[i]\) 最长的长度 k满足前 k 位 后 k 位\(ki\)这个长度叫Border。例\(Pabcab\)长度 5 前缀a ab abc abca abcab 后缀b ab cab bcab abcab 最长相等真前后缀是ab长度 2 → \(next[5]2\)。2. next 数组求解逻辑1-based和你板子统一j 记录上一个前缀的最长 border 长度\(next[1]0\)单个字符无真前后缀i 从 2 遍历到 m若 \(P[i-1] \ne P[j]\)\(jnext[j]\) 回溯直到 \(j0\)匹配相等\(j\)\(next[i]j\)。 全程只前进不回退\(O(m)\) 求出 next。3. Border 的关键作用KMP 灵魂当匹配到 \(P[j]\) 和文本失配时 \(P[1,j-1]\) 是已经匹配成功的一段不需要全部重比。 利用 \(next[j-1]k\)说明 \(P[1,k] P[j-k,j-1]\)直接把 j 跳到 k文本指针 i 不动。举例 \(Pabcabc\)匹配到第 6 位失配\(next[6]3\)直接让 \(j3\)拿 \(P[3]\) 继续和当前文本字符对比省去从头匹配。三、KMP 匹配主流程设文本 S模式 Pi 文本下标j 模式下标循环遍历文本每个字符 \(S[i]\)失配且 \(j0\)\(jnext[j]\)若字符相等\(i,j\)当 \(jm\)模式完全匹配记录匹配起点\(jnext[j]\) 寻找重叠匹配比如aaaa中aa会多次匹配。全程 i 只增不减总复杂度 \(O(nm)\)。四、nextval优化失配数组原理问题普通 next 存在无效跳转例 \(Paaaaa\)\(next[4]3\)若 \(P[4]P[3]a\) 失配时跳到 \(j3\)字符还是 a依然失配多一次无用判断。nextval 优化规则对每个 i\(knext[i]\)若 \(P[i-1] P[k]\)继续令 \(knext[k]\)直到字符不等或 \(k0\)\(nextval[i]k\)。作用失配时一步跳到字符不同的位置减少比较次数卡常专用。五、拓展Border 衍生知识点1. 最小循环节字符串总长 L最长 border \(knext[L]\)循环节长度 \(dL-k\)。若 \(L \% d 0\)整个串由 \(L/d\) 个相同子串重复否则最小循环节是自身。 例abcabcabc\(L9,next[9]6,d3\)可由abc重复 3 次构成。2. 所有 Border 数量cnt 数组动物园题\(cnt[i]\) 前缀 i 所有合法 border 的总个数 递推式\(cnt[i] cnt[next[i]] 1\) 含义最长 border 最长 border 的所有 border。3. 不重叠 bordernum 数组NOI 动物园要求 \(2k \le i\)前后缀不重叠用双指针维护最大合法 k\(num[i]cnt[k]\)最后累乘 \((num[i]1)\) 得答案。