KMP模板

佚名 6年前 (2019-04-11) 随笔 1087人围观抢沙发百度已收录

 1 int strstr(char* s, char* t)
 2 {
 3     int next[100005];
 4     next[0]=-1;
 5     int j=0,k=-1;
 6     while(t[j]!='\0'){
 7         if(k==-1||t[j]==t[k]){
 8             next[++j]=++k;
 9         }
10         else{
11             k=next[k];
12         }
13     }
14     j=0,k=0;
15     while(k==-1||(s[j]!='\0'&&t[k]!='\0')){
16         if(k==-1||s[j]==t[k]){
17             j++,k++;
18         }
19         else{
20             k=next[k];
21         }
22     }
23     if(t[k]=='\0')
24         return j-k;
25     return -1;
26 }