题解 P3375 【【模板】KMP字符串匹配】
teafrogsf
2017-07-23 09:16:14
题解里都是大神，想必他们的代码更加完美~~**比如楼下的yyb大神**~~，所以这里只是想要说一下C++党在这个题目提交的注意事项：
1、不要用玄学getline，否则直接全WA
2、用scanf注意getchar，偶尔舍弃一下string也是不错的XD
3、cincout会超时，不过可以关闭流同步(std::ios::sync\_with\_stdio(false))
4、不要像我一样傻傻的多次执行KMP(这样是84分)
当然，代码还是要贴的，不过可能有点丑233333
```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define f(i,a,b) for(i=a;i<=b;++i)
int next[10010];
int m;
char s[1000010],p[1010];
void get()//这个next有一点略微的不同
{
int pz=strlen(p);
next[0]=-1;
int k=-1,j=0;
while(j<pz)
{
//printf("%d %d\n",k,j);
if(k==-1||p[j]==p[k])
{
++j,++k;
next[j]=k;
}
else k=next[k];
}
}
void find()//KMP核心算法，但我感觉求next才是核心
{
int i=0,j=0;
int sz=strlen(s),pz=strlen(p);
while(i<sz)
{
if(j==-1||s[i]==p[j])++i,++j;
else j=next[j];
if(j==pz)
{
printf("%d\n",i-j+1);
j=next[j];
}
}
}
int main()
{
int i,j;
scanf("%s",s),getchar(),scanf("%s",p);
get();
find();
f(i,1,strlen(p))printf("%d ",next[i]);putchar('\n');
return 0;
}
```