P3375 【模板】KMP字符串匹配

2019-8-27 8:03

1,111

未分类

87 字

1 分钟内

链接：P3375

------------------------------

思路：理论版

　　通俗易懂版

KMP主要就是有一个next数组，这个数组可以让我们在匹配不成功的时候不用去从开始的位置+1去匹配，而是直接“

跳”过来，来做到o(n+m)的复杂度的

#include<iostream>
#include<cstring>
#include<iostream>

using namespace std;
char a[1000100],b[1000100];
int ne[1000100];
int main(){
    scanf("%s%s",a+1,b+1);
    int la=strlen(a+1),lb=strlen(b+1);
    int j=0;
    ne[1]=ne[0]=0;
    for(int i=2;i<=lb;++i){
        while(j&&b[i]!=b[j+1]) j=ne[j];
        if(b[i]==b[j+1]) j++;
        ne[i]=j;
    }
    j=0;
    for(int i=1;i<=la;++i){
        while(j&&a[i]!=b[j+1]) j=ne[j];
        if(a[i]==b[j+1]) j++;
        if(j==lb){
            printf("%dn",i-lb+1);
            j=ne[j];
        }
    }
    for(int i=1;i<=lb;++i)
        cout<<ne[i]<<" ";
    return 0;
}