KMP

模板

 1 int Next[MAXN];
 2 char s1[MAXN],s2[MAXN];
 3 
 4 void getNext(char *s){
 5     int l = strlen(s);
 6     Next[0] = -1;//很关键,漏了会死循环.
 7     int k=-1,j=0;
 8     while(j<l){
 9         if(k==-1 || s[k] == s[j]){
10             j++;
11             k++;
12             //Next[j] = k;//这句是未优化时写的代码
13             if(s[j] != s[k])//如果是k=-1的话,直接赋值为-1,这样优化可以降低一些复杂度
14                 Next[j] = k;
15             else
16                 Next[j] = Next[k];
17         }
18         else{
19             k=Next[k];
20         }
21     }
22 }
23 
24 int kmp(char *s1,char *s2){
25     getNext(s2);//注意,求next数组是求匹配串的
26     int l1=strlen(s1);
27     int l2=strlen(s2);
28     int i=0;
29     int j=0;
30     while(i<l1&&j<l2){//随机应变，例如求匹配串有多少个，此处的j<l2去掉即可
31         if(j==-1||s1[i] == s2[j]){//找到匹配各自加1
32             i++;
33             j++;
34         }
35         else{//kmp的精髓,自己好好体悟
36             j=Next[j];
37         }
38     }
39     if(j==l2){
40         return i-j;//找到匹配串，返回第一个匹配的位置
41     }
42     else return -1;
43 }

int Next[MAXN];

char s1[MAXN],s2[MAXN];

voidgetNext(char*s){

    int l =strlen(s);

    Next[0]=-1;//很关键,漏了会死循环.

    int k=-1,j=0;

    while(j<l){

        if(k==-1|| s[k]== s[j]){

            j++;

            k++;

            //Next[j] = k;//这句是未优化时写的代码

            if(s[j]!= s[k])//如果是k=-1的话,直接赋值为-1,这样优化可以降低一些复杂度

                Next[j]= k;

            else

                Next[j]= Next[k];

        else{

            k=Next[k];

intkmp(char*s1,char*s2){

    getNext(s2);//注意,求next数组是求匹配串的

    int l1=strlen(s1);

    int l2=strlen(s2);

    int i=0;

    int j=0;

    while(i<l1&&j<l2){//随机应变，例如求匹配串有多少个，此处的j<l2去掉即可

        if(j==-1||s1[i]== s2[j]){//找到匹配各自加1

            i++;

            j++;

        else{//kmp的精髓,自己好好体悟

            j=Next[j];

    if(j==l2){

        return i-j;//找到匹配串，返回第一个匹配的位置

    elsereturn-1;