KMP

#include<iostream>
#include<string>
using namespace std;

const int maxm = 10010;
const int maxn = 200010;
int a[maxn],b[maxm],Next[maxm];

void init(int p[],int m)
{
	Next[0] = -1;
	int i = 0, j = -1;
	while (i < m)
	{
		if (j == -1 || p[i] == p[j])
			Next[++i] = ++j;
		else
			j = Next[j];
	}
}

int find(int t[], int p[],int n,int m)
{
	int i = 0;
	int j = 0;
	while (i < n&&j < m)
	{
		if (j == -1 || t[i] == p[j])
		{
			i++;
			j++;
		}
		else
			j = Next[j];
	}
	if (j == m)
		return i - j + 1;
	return -1;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 0; i < n; ++i)
			cin >> a[i];
		for (int i = 0; i < m; ++i)
			cin >> b[i];
		init(b, m);
		cout << find(a,b,n,m)<<endl;
	}
	return 0;
}

留下评论