kmp算法：

自学kmp算法：

first time：wa

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

const int maxn=+;

char s1[maxn],s2[maxn];

int next[maxn],n,m;

int main()

{

    scanf("%s%s",s1+,s2+);

    n=strlen(s1+);m=strlen(s2+);

    next[]=;

    for(int i=;i<=m;++i){//1~j的前后缀最大值

        if(i==)printf("!");

        int j=next[i-];

        printf("j%d ",j);

        while( s1[i]!=s2[j+] && j ){j=next[j];printf("j%d ",j);}

        if(s1[i]==s2[j+])j++;

        printf("final:%d\n",j);

        next[i]=j;

    //    printf("next[%d]%d ",i,next[i]);

    }

    int j=;

    for(int i=;i<=n;i++){//i未匹配，j已匹配

        while(s1[i]!=s2[j+] && j)j=next[j];

        if(s1[i]==s2[j+])j++;

        if(j==m){

        printf("%d\n",i-m+);

        j=next[j];

        }

    }

    for(int i=;i<=m;i++){

    //    printf("%d ",next[i]);

    }

    return ;

}

/*

ababababababbbabbbabbbababababb

abbbabaabbbabbb

*/

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

const int maxn=+;

char s1[maxn],s2[maxn];

int next[maxn],n,m;

int main()

{

    scanf("%s%s",s1+,s2+);

    n=strlen(s1+);m=strlen(s2+);

    next[]=;

    for(int i=;i<=m;++i){//1~j的前后缀最大值

        //if(i==3)printf("!");

        int j=next[i-];

        //printf("j%d ",j);

        while( s2[i]!=s2[j+] && j )j=next[j];//printf("j%d ",j);}

        if(s2[i]==s2[j+])j++;

        //printf("final:%d\n",j);

        next[i]=j;

    //    printf("next[%d]%d ",i,next[i]);

    }

    int j=;

    for(int i=;i<=n;i++){//i未匹配，j已匹配

        while(s1[i]!=s2[j+] && j)j=next[j];

        if(s1[i]==s2[j+])j++;

        if(j==m){

        printf("%d\n",i-m+);

        j=next[j];

        }

    }

    for(int i=;i<=m;i++){

        printf("%d ",next[i]);

    }

    return ;

}
易错点分析：
kmp算法的基本思想就是
利用最长前后缀
减少重复匹配次数
预处理模式串时，自己与自己匹配，主串不参与
还有就是：循环中变量的意义不要混淆，
比如next[i]->模式串中1~i子串的最大前后缀，所以包括字母s2[i]
while（ __!=__ &&   ）注意下标
...