题目描述

给定两个数字串 $a$ 和 $b$，你需要找出数字串 $b$ 第一次出现在数字串 $a$ 中的起始位置。

输入格式

输入包含多组数据。

第一行是一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行包含两个整数 $n_a$ 和 $n_b$，分别表示数字串 $a$ 和 $b$ 的长度。保证 $n_a, n_b \leq 10^6$。
• 第二行包含 $n_a$ 个整数，表示数字串 $a$。
• 第三行包含 $n_b$ 个整数，表示数字串 $b$。

输出格式

对于每组数据，输出一个整数，表示数字串 $b$ 第一次出现在数字串 $a$ 中的起始位置（从 $1$ 开始计数）。如果数字串 $b$ 不在 $a$ 中，则输出 $-1$。

Samples

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

6

提示

在样例中：

• 数字串 $a = [1, 2, 1, 2, 3, 1, 2, 3, 1, 3, 2, 1, 2]$。
• 数字串 $b = [1, 2, 3, 1, 3]$。
• 数字串 $b$ 第一次出现在数字串 $a$ 的第 $6$ 个位置（从 $1$ 开始计数）。

本题所有数据都必须使用快读快写！！！

void read(int &n)
{
    bool w = 0;
    char c = getchar();
    for(; c < 48 || c > 57; c = getchar())
        w = c == 45;
    for(n = 0; c >= 48 && c <= 57; c = getchar())
        n = n * 10 + c - 48;
    n = w ? -n : n;
}
void write(int x, char a)
{
    char c[40], s = 0;
    if(x < 0) putchar(45), x = -x;
    for(; x ;) c[s ++] = x % 10, x /= 10;
    if(!s) putchar(48);
    for(; s -- ;) putchar(c[s] + 48);
    putchar(a);
}

#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
	x=0;
	int f=1;
	char ch=getchar();
	for(; !isdigit(ch); ch=getchar())if(ch=='-')f=-f;
	for(; isdigit(ch); ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
	x*=f;
}
int p[1005001],n,m,k,a[1005001],b[1005001],lena,lenb,j;
int main() {
	read(k);
	while(k--) {
		p[1]=0;
		read(lena),read(lenb);
		j=0;
		for(int i=1; i<=lena; i++) read(a[i]);
		for(int i=1; i<=lenb; i++) read(b[i]);
		for(int i=1; i<lenb; i++) {
			while(j>0&&b[i+1]!=b[j+1]) j=p[j];
			if(b[j+1]==b[i+1])j++;
			p[i+1]=j;
		}
		j=0;
		bool bo=1;
		for(int i=0; i<lena; i++) {
			while(j>0&&b[j+1]!=a[i+1]) j=p[j];
			if(b[j+1]==a[i+1])
				j++;
			if(j==lenb) {
				printf("%d\n",i-lenb+2);
				bo=0;
				break;
			}
		}
		if(bo) puts("-1");
	}
	return 0;
}

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
void read(int &n)
{
    bool w = 0;
    char c = getchar();
    for(; c < 48 || c > 57; c = getchar())
        w = c == 45;
    for(n = 0; c >= 48 && c <= 57; c = getchar())
        n = n * 10 + c - 48;
    n = w ? -n : n;
}
void write(int x, char a)
{
    char c[40], s = 0;
    if(x < 0) putchar(45), x = -x;
    for(; x ;) c[s ++] = x % 10, x /= 10;
    if(!s) putchar(48);
    for(; s -- ;) putchar(c[s] + 48);
    putchar(a);
}

const int N=1e6+10,base=233331;
int s1[N],s2[N];
int n1,n2;
unsigned long long f1[N],f2[N],G[N];
void init(){
    G[0]=1;
    rep(i,1,n1)G[i]=G[i-1]*base;
    rep(i,1,n1)f1[i]=f1[i-1]*base+s1[i];
    rep(i,1,n2)f2[i]=f2[i-1]*base+s2[i];
}
unsigned long long calc(int l,int r){
    return f1[r]-f1[l-1]*G[r-l+1];
}
void solve(){
    read(n1);read(n2);
    rep(i,1,n1)read(s1[i]);
    rep(i,1,n2)read(s2[i]);
    init();
    rep(i,1,n1-n2+1)if(calc(i,i+n2-1)==f2[n2]){write(i,'\n');return;}
    write(-1,'\n');
}
main(){
    int T;
    read(T);
    for(;T;--T){
        solve();
    }
}