AcWing 831. KMP字符串
原题链接
简单
作者:
Karma
,
2019-10-25 17:06:03
,
所有人可见
,
阅读 639
#include <iostream>
#include <cstdio>
using namespace std;
const int M = 1e5 + 10;
const int N = 1e4 + 10;
char s[M];
char p[N];
int ne[N];
int main()
{
int n;
cin >> n;
scanf("%s", p+1);
int m;
cin >> m;
scanf("%s", s+1);
// ne[1] = 0;
for(int i = 2, j = 0; i <= n; ++ i)
{
while(j > 0 && p[i] != p[j+1])
{
j = ne[j];
}
if(p[i] == p[j+1])
{
++ j;
ne[i] = j;
}
else
{
// ne[i] = 0;
}
}
for(int i = 1, j = 0; i <= m; ++ i)
{
while(j > 0 && s[i] != p[j+1])
{
j = ne[j];
}
if(s[i] == p[j+1])
{
++ j;
if(j == n)
{
cout << i-n+1 - 1 << " ";
j = ne[j];
}
else
{
}
}
else
{
}
}
}