KMP
KMP 算法是给定一个源字符串 S (蓝色), 和一个模板字符串 P (红色), 在 S 中去寻找 P 字符串, 并给出 P 在 S 字符串当中开始的下标
next[j]=k 的含义是: 以 P[j] 为结尾的模板串, 其前缀与后缀相等的最大长度为 k
设源串 S 与 模板串 P, 每下一步都是比较 s[i] 与 p[j+1] 是否相等, 如果相等的话就继续, 如果不相等, 则就把 P 字符串后移, 再重新尝试去匹配, 因为每次比较的是 s[i] 与 p[j+1], 所以这要减少 j 就能起到后移的效果, 先减小到 next[j], 不能继续匹配的话就继续减小, 直到 0 为止, 到 0 就说明 P 要从头开始尝试匹配了
求 next 数组就是先拿 P 去匹配自己(P)
如果 p[i]==p[j+1], 则 next[i]=j+1, 否则 next[i]=j=0(此时 j 一定等于 0, 也就是 next[i]=0, 表示需要从头开始)
831. KMP字符串 - AcWing题库
#include<iostream> using namespace std; const int NN=1e5+10, MM=1e6+10; char p[NN], s[MM]; int n, m; int ne[NN]; // 不用 next 这个单词, 防止重名 int main(){ // KMP 算法让数组从下标 1 开始方便操作 scanf("%d%s", &n, p+1); scanf("%d%s", &m, s+1); // 用 p 匹配 p 来求 ne 数组的值 // i 从 2 开始遍历就可以了, ne[1] 一定为 0 for(int i=2, j=0;i<=n;i++){ while(j && p[i]!=p[j+1]) j=ne[j]; // 减小 j , 使得 p[i]==p[j+1], 或者直到 j==0 为止 if(p[i]==p[j+1]) j++; ne[i]=j; } for(int i=1, j=0;i<=m;i++){ while(j && s[i]!=p[j+1]) j=ne[j]; if(s[i]==p[j+1]) j++; if(j==n){ printf("%d ", i-n); // 本来应该是 i-n+1, 这里要把下标从 1 开始转回从0开始 j=ne[j]; // 继续向后匹配 } } cout<<endl; return 0; }
