kmp算法模板

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N = 1005;
4. char str[N], pattern[N];
5. int Next[N];
6. 
7. void getNext(char *p, int plen){     //计算Next[1]~Next[plen]
8. Next[0]=0; Next[1]=0;
9. for(int i=1; i < plen; i++){  //把i的增加看成后缀的逐步扩展
10.         int j = Next[i];          //j的后移：j指向前缀阴影w的后一个字符
11.         while(j && p[i] != p[j])  //阴影的后一个字符不相同
12.             j = Next[j];          //更新j
13. if(p[i]==p[j])   Next[i+1] = j+1;
14. else             Next[i+1] = 0;
15.     }
16. }
17. void kmp(char *s, char *p) {         //在s中找p
18.     int last = -1;
19.     int slen=strlen(s), plen=strlen(p);
20.     getNext(p, plen);               //预计算Next[]数组
21.     int j=0;
22. for(int i=0; i<slen; i++) {     //匹配S和P的每个字符
23.         while(j && s[i]!=p[j])      //失配了。注意j==0是情况(1)
24.              j=Next[j];             //j滑动到Next[j]位置
25. if(s[i]==p[j])  j++;        //当前位置的字符匹配，继续
26. if(j == plen) {             //j到了P的末尾，找到了一个匹配
27. //匹配了一个，在S中的起点是i+1-plen，末尾是i。如有需要可以打印：
28.                printf("Location=%d, %s\n", i+1-plen,&s[i+1-plen]);
29.         }
30.     }
31. }
32. int main(){
33.     scanf("%s", str);          //读串S
34.     scanf("%s", pattern);      //读模式串P
35.     kmp(str, pattern);
36. return 0;
37. }