1711.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<stdio.h>
#define SMAX 1000001
#define PMAX 10001
int s[SMAX],p[PMAX];
int s_len,p_len;
int nextv[PMAX];
int main()
{
    int test,i,j;
    scanf("%d",&test);
    while(test--){
        scanf("%d %d",&s_len,&p_len);
        for(i=0;i<s_len;i++)
            scanf("%d",&s[i]);
        for(i=0;i<p_len;i++)
            scanf("%d",&p[i]);
        i=0,j=-1;
        nextv[0]=-1;
        while(i<p_len-1){
            if(j==-1||p[i]==p[j]){
                i++,j++;
                nextv[i]=j;
            }
            else
                j=nextv[j];
        }
        i=0,j=0;
        while(i<s_len&&j<p_len){
            if(j==-1||s[i]==p[j])
                i++,j++;
            else
                j=nextv[j];
        }
        if(j==p_len)
            printf("%d\n",i-p_len+1);
        else
            printf("-1\n");
    }
    return 0;
}