Number Sequence （KMP第一次出现位置）

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample 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

Sample Output

6

-1

思路：将第一次出现的i减去自身长度就可以了

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

void kmp_pre(int x[],int m,int next[]) {

	int i,j;

	j=next[0]=-1;

	i=0;

	while(i<m) {

		while(-1!=j && x[i]!=x[j])j=next[j];

		next[++i]=++j;

	}

}

int next1[1000010];

int KMP_Count(int x[],int m,int y[],int n) { //x 是模式串，y 是主串

	int i,j;

	int ans=-1;

//preKMP(x,m,next);

	kmp_pre(x,m,next1);

	i=j=0;

	while(i<n) {

		while(-1!=j && y[i]!=x[j])j=next1[j];

		i++;

		j++;

//		cout<<m<<endl;

		if(j>=m) {

			ans=i+1-m;

//		    cout<<next[j]<<endl;

			j=next1[j];

			break;

		}

	}

	return ans;

}

int  a[10005];

int b[1000005];

int main() {

	int T;

	cin>>T;

	int lena,lenb;

	while(T--) {

		scanf("%d %d",&lena,&lenb);

	    for(int t=0;t<lena;t++)

	    {

	    	scanf("%d",&a[t]);

		}

		for(int t=0;t<lenb;t++)

		{

			scanf("%d",&b[t]);

		}

		printf("%d\n",KMP_Count(b,lenb,a,lena));

	}

	return 0;

}

巴特西

Number Sequence （KMP第一次出现位置）

最新文章

热门文章