KMP算法经典代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    }
}
int KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n&&j<m){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
    }
    return i-j;
}

发表评论

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