hdu 1711 Number Sequence

直接套KMP模板

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int s[1000005],w[10005],next[10005];
int b,c;
void show()
{
    int i,j;
    i=0;
    next[0]=-1;
    j=-1;
    while(i<c)
    {
        if(j==-1||w[i]==w[j])
            {i++;
            j++;
            next[i]=j;
            }
            else
                j=next[j];
    }
}
int KMP()
{
    int i,j;
    i=0;
    j=0;
    while(i<b&&j<c)
    {
        if(j==-1||w[j]==s[i])
        {
            i++;
            j++;
        }
        else
        j=next[j];
    }
    if(j>=c)
        return i-j+1;
    else
        return -1;
}
int main()
{
    int a;
    scanf("%d",&a);
    while(a--)
    {
        scanf("%d %d",&b,&c);
        for(int i=0;i<b;i++)
            scanf("%d",&s[i]);
        for(int j=0;j<c;j++)
            scanf("%d",&w[j]);
        show();
        int ans=KMP();
        printf("%d\n",ans);
    }
    return 0;
}

hdu 1711 Number Sequence,布布扣,bubuko.com

hdu 1711 Number Sequence

原文：http://blog.csdn.net/asuxiexie/article/details/38022941