AcWing 833. KMP字符串
原题链接
简单
作者:
Chandler丶
,
2024-02-18 23:14:33
,
所有人可见
,
阅读 32
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
#define ll long long
const int N =100010, M = 1000010;
char p[N],s[M];
int n,m;
int ne[N];
int main()
{
cin >> n >> p+1 >> m >> s+1;
//求next的过程
for(int i =2,j = 0;i <=n;i++)
{
while(j && p[i] !=p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
//kmp的匹配过程
for(int i = 1,j = 0 ;i <= m;i++)
{
while(j && s[i] != p[j+1]) j =ne[j]; // 如果不匹配,j就后退
if(s[i] == p[j+1]) j++; //如果匹配了,那就j向前移动
if(j == n) //匹配成功
{
printf("%d ",i - n);
j = ne[j];
}
}
return 0;
}