AcWing 831. KMP字符串
原题链接
简单
#include <iostream>
using namespace std;
const int N = 1000010;
char p[N],s[N];
int n,m;
int ne[N];
int main(){
cin >> n >> (p+1) >> m >> (s+1);
for(int i = 2, j = 0; i <= n; i ++){ //求next数组,定义i从第二个元素开始遍历
while(j && p[i] != p[j + 1]) j = ne[j]; //j指针进行回溯
if(p[i] == p[j+1]) j ++; //j指针后移
ne[i] = j; //求出next数组各个元素值
}
for(int i = 1, j = 0; i <= m; i ++){ //匹配过程,其实原理和next类似,i指向长的数组s,j指向pm数组
while(j && s[i] != p[j + 1]) j = ne[j]; //匹配不成功,j进行回溯,也就是只对pm数组进行操作,i指针继续向后
if(s[i] == p[j+1]) j ++; //匹配成功后,j指针后移
if(j == n){
printf("%d ",i - n); //简单理解为数组s匹配成功字段结尾的位置减去pm数组的长度获得起始位置
j = ne[j]; //将j指针进行回溯回到pm数组的头位置
}
}
return 0;
}