数据结构-KMP字符串模式匹配算法实现 （C++代码）

解题思路:





注意事项:





参考代码:

#include <cstdio>

#include <cstring>

char s1[1000005],s2[10005];

int next[10005];

int lens1,lens2;

void getnext()

{

    int i=0,j=-1;

    next[0]=-1;

    while(i<lens2)

    {

        if(j==-1||s2[i]==s2[j])

        {

            i++;

            j++;

            next[i]=j;

        }

        else

            j=next[j];

    }

}

int KMP()

{

    getnext();

    int i=0,j=0;

    while(i<lens1)

    {

        if(j==-1||s1[i]==s2[j])

        {

            i++;

            j++;

        }

        else

            j=next[j];

        if(j==lens2)

        {

            return i-lens2+1;

        }

    }

    return 0;

}

int main()

{

    while(scanf("%s %s",s1,s2)!=EOF)

    {

        getchar();

        lens1=strlen(s1);

        lens2=strlen(s2);

        printf("%d\n",KMP());

    }

    return 0;

}