soj2307kmp.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 57 行

#include<stdio.h>
#include<string.h>


int next[1000000];
char a[1000000],b[1000000];

int KMP(char *pat,char *goal)
{
    int sum=0;
    int lenp=strlen(pat),leng=strlen(goal);
    int i=0,j=0;
    while(i<leng)
    {
        if(j==-1){i++;j=0;}
        else if(pat[j]==goal[i]){++i;++j;}
        else j=next[j];
        if(j>=lenp)
        {
            sum++;
        }
    }
    return sum;
}

void getnext(char *pat,int next[])
{
    next[0]=-1;
    int i=0,j=-1,lenp=strlen(pat);
    while(i<lenp)
    {
        if(j==-1||pat[i]==pat[j])
        {
            ++i;++j;next[i]=j;
        }
        else j=next[j];
    }
}



int main(void)
{
    int t;
    scanf("%d",&t);getchar();
    while(t--)
    {
        scanf("%s %s",a,b);
        getchar();
        getnext(b,next);
        int len;
        len=KMP(b,a);
        printf("%d\n",len);
    }
    return 0;
}