RT

题目

给定两个数字序列：a[1]、a[2]、......、a[N] 和 b[1]、b[2]、......、b[M] （1 <= M <= 10000，1 <= N <= 1000000）。你的任务是找到一个数字 K 使得 a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[米]。如果存在多于一个 K，则输出最小的一个。
输入

输入的第一行是一个数字 T，它表示案例的数量。每个案例包含三行。第一行是两个数字 N 和 M (1 <= M <= 10000, 1 <= N <= 1000000)。第二行包含 N 个整数，分别表示 a[1]、a[2]、......、a[N]。第三行包含 M 个整数，分别表示 b[1]、b[2]、......、b[M]。所有整数都在 [-1000000, 1000000] 的范围内。

输出
对于每个测试用例，您应该输出仅包含上述 K 的一行。如果不存在这样的 K，则输出 -1。

Input
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

Output
6
-1

代码

#include<iostream>
#include<algorithm>
#include<iostream>
using namespace std;
int nxt[10010],T,n,m,a[1000010],b[10010],t,p,mn=0x3f3f3f;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        p=-1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&b[i]);
        }
        for (int i=2,j=0;i<=m;i++)
        {     
            while(j&&b[i]!=b[j+1])
                j=nxt[j];    
            if(b[j+1]==b[i])j++;    
            nxt[i]=j;
        }
        for(int i=1,j=0;i<=n;i++)
        {
            while(j>0&&b[j+1]!=a[i])
                j=nxt[j];
            if (b[j+1]==a[i]) 
                j++;
            if (j==m)
            {
                p=1;
                mn=min(mn,i-m+1);
                j=nxt[j];
            }
        }
        if(p==-1) printf("-1\n");
        else printf("%d\n",mn);
    }
}