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