模板

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

 

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

        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
    

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

            i++;

            j++;

        }

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

            j=Next[j];

        }

    }

    if(j==l2){

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

    }

    elsereturn-1;

}