题解 P3375 【【模板】KMP字符串匹配】

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

#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;
}