//2305327 2010-04-07 10:46:48 Accepted 1711 2015MS 4308K 846 B C++ Xredman 

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

const int N = 1000002;
int next[N];
int S[N], T[N];
int slen, tlen;
void getNext()
{
	int j, k;
	j = 0; k = -1; next[0] = -1;
	while(j < tlen)
		if(k == -1 || T[j] == T[k])
			next[++j] = ++k;
		else
			k = next[k];

}

int KMP_Index()
{
	int i = 0, j = 0;
	getNext();

	while(i < slen && j < tlen)
	{
		if(j == -1 || S[i] == T[j])
		{
			i++; j++;
		}
		else
			j = next[j];
	}
	if(j == tlen)
		return i - tlen;
	else
		return -1;
}
int main()
{
	
	int TT;
	int i, cc;
	cin>>TT;
	while(TT--)
	{
		cin>>slen>>tlen;
		for(i = 0; i < slen; i++)
			cin>>S[i];
		for(i = 0; i < tlen; i++)
			cin>>T[i];
		cc = KMP_Index();
		if(cc == -1)
			cout<<cc<<endl;
		else
			cout<<cc + 1<<endl;
	}
	return 0;
}

• 相关文章
• 全局相关文章