【模板】kmp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e5+5;
 4 int next[amn];
 5 int kmp_search(char *s,char *p){
 6     int slen=strlen(s),plen=strlen(p);
 7     int i=0,j=0;
 8     while(i<slen&&j<plen){
 9         if(j==-1||s[i]==p[j])i++,j++;
10         else j=next[j];
11     }
12     if(j==plen)return i-j;
13     else return -1;
14 }
15 void GetNext(char *p,int next[]){
16     int plen=strlen(p);
17     next[0]=-1;               ///next是上一个字符对应的前缀等于后缀的最长长度
18     int k=-1,j=0;             ///因为字符串下标从0开始，所以最长长度也是前缀最后一个字符的下一个字符的下标（index）（前缀与后缀相等的最长长度0对应第一个字符，1对应第2个...这样保证这一位之前的字符是匹配的（因为现在已经知道前缀与后缀匹配）)
19     while(j<plen-1){          ///k是上一个状态的next,若j==plen-1则此为是最后一个字符，其后没有字符，故不需求出下一个字符的next
20         if(k==-1||p[j]==p[k]){///k==-1在前面判断为真就直接执行下一条语句而不会造成数组越界
21             k++,j++;
22             if(p[j]!=p[k])
23                 next[j]=k;
24             else              ///若p[j]==p[k]且p[j]!=s[i],则下次用p[k]匹配仍是失效的，故要用p[next[k]](若p[j]!=p[next[k]]来和s[i]匹配
25                 next[j]=next[k];
26         }
27         else k=next[k];
28     }
29 }
30 int main(){
31     char s[]="hello",p[]="ll";
32     GetNext(p,next);
33     printf("pos: %d\n",kmp_search(s,p));
34 }