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

2018-01-21 10:17:17


首先要说的是:千万不要用gets!!(坑死我了)

然后,正文如下:

KMP一开始看有点晕,你先要知道的是,它是先自己和自己弄,再和大串弄。

虽然我不是P党,但这篇讲稿不错:http://www.matrix67.com/blog/archives/115

i是a串(大串)的指针,j是b串(小串)的指针

当你匹配到j==m时,你就胜利了,此时在a串里的出现位置就是i-m+1

那么,平常的一位一位匹配,不行再i+1从头开始太慢了,明明b串前面里有和当前后面相同几位,你却又要把它重新匹配一遍。。

like:

ababababe

ababe

啊,你发现这里炸了,因为b[1]=b[3],b[2]=b[4]你完全可以,直接这样:

ababababe

.....ababe

而不是这样:

ababababe

..ababe

于是,你想到了,可以预处理出相同的部分,怎么处理列

我们完全可以预处理出这样一个数组p[j],表示当匹配到b数组的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少。p[j]应该是所有满足b[1..p[j]]=b[j-p[j]+1..j]的最大值。

这样可以使得A[i-j+1..i]与B[1..j]保持匹配(此处为新的j)。

然后,下一位如果还是不能匹配,再把前一个j翻出来,再匹配一次,直到找不到相同的前缀了也就是j=0了,就只能把整个串往后挪一位了

本人可能讲的不清楚,大家看看上面那篇讲稿会好一点

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    char a[1000100],b[1000100];
    int p[1000100];
    int main()
    {
        scanf("%s%s",a+1,b+1);
        int la=strlen(a+1),lb=strlen(b+1);
        int j=0;
        p[1]=0;
        //先处理出p数组,无非是b和自己匹配,与b和a匹配一样,故代码差不多
        for(int i=2;i<=lb;i++)
        {
            while(j>0 && b[i]!=b[j+1]) j=p[j];//往前翻记录了有相同前缀的j
            if(b[i]==b[j+1]) j++;//i匹配成功了,i继续往后
            p[i]=j;
        }
        j=0;
        for(int i=1;i<=la;i++)
        {
            while(j>0 && a[i]!=b[j+1]) j=p[j];
            if(a[i]==b[j+1]) j++;
            if(j==lb) printf("%d\n",i-lb+1),j=p[j];
        }
        for(int i=1;i<lb;i++)
            printf("%d ",p[i]);
        printf("%d",p[lb]);
        return 0;
    }
本人萌新,还请大神指教