HDU5918【KMP大法好，虽然我不会】

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAX=1000010;

int n,m;

int a[MAX],b[MAX];

int nextval[MAX];

LL ans;

void get_next(int b[],int m)

{

    int i=0;

    nextval[0]=-1;

    int j=-1;

    while(i<m)

    {

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

        {

            ++i;

            ++j;

//            if(b[i]==b[j])

//                nextval[i]=nextval[j];

//            else

                nextval[i]=j;

        }

        else

            j=nextval[j];

    }

}

int KMP(int a[],int n,int b[],int m,int nextval[],int pos,int p)

{

    int i=pos;

    int j=0;

    while(i<n)

    {

        if(j==-1||a[i]==b[j])

        {

            i+=p;

            j++;

            if(j==m)

            {

                j=nextval[j];

                ans++;

            }

        }

        else

            j=nextval[j];

    }

}

int main()

{

    int t,i,j;

    int cas=1;

    scanf("%d",&t);

    while(t--)

    {

        int p;

        ans=0;

        scanf("%d%d%d",&n,&m,&p);

        for(i=0; i<n; ++i)

            scanf("%d",&a[i]);

        for(j=0; j<m; ++j)

            scanf("%d",&b[j]);

        get_next(b,m);

//        for(i=0; i<m; i++)

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

        for(i=0;i<p;i++)

        {

            if(i+(m-1)*p>=n)

                break;

            KMP(a,n,b,m,nextval,i,p);

        }

        printf("Case #%d: %lld\n",cas++,ans);

    }

    return 0;

}
巴特西

HDU5918【KMP大法好，虽然我不会】

最新文章

热门文章
