<span>浅谈kmp</span>

 1 void getNext(char *p){    //比上边的nt数组往后一位
 2     nt[0]=-1;
 3     int i=0,j=-1;       //j控制前缀,i控制后缀
 4     int lp=strlen(p);
 5     while(i<lp){
 6         if(j==-1||p[i]==p[j]){
 7             ++i;++j;
 8             nt[i]=j;
 9         }
10         else j=nt[j];
11     }
12 }

 1 int kmp(char *t,char* p){
 2     getNext(p);
 3     int i=0,j=0;
 4     int lt=strlen(t),lp=strlen(p);
 5     int ans=0;
 6     while(i<lt){
 7         if(j==-1||t[i]==p[j]){
 8             i++;
 9             j++;
10         }
11         else j=nt[j];
12         if(j==lp) ans++;
13     }
14     return ans;
15 }