洛谷 【模板】KMP字符串匹配

题号:3375

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int _next[10000];
void buildNext(char * P){
    int m=strlen(P),j=0;
    int t=_next[0]=-1;
    while(j<m){
        if(t<0||P[j]==P[t]){
            _next[++j]=++t;
        }else
            t=_next[t];
    }
}
void KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
        if(j==m){
            printf("%d\n",i-j+1);
            j=_next[j];
        }
    }
}
int main(){
    char P[10000],T[20000000];
    scanf("%s%s",T,P);
    buildNext(P);
    int lenP=strlen(P);
    KMP(P,T);
    for(int i=1;i<=lenP;i++){
        printf("%d ",_next[i]);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注