Given two sequences of numbers : a11, a22, ...... , aNN, and b11, b22, ...... , bMM (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make aKK = b11, aK+1K+1 = b22, ...... , aK+M−1K+M−1 = bMM. If there are more than one K exist, output the smallest one.
InputThe 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 a11, a22, ...... , aNN. The third line contains M integers which indicate b11, b22, ...... , bMM. All integers are in the range of −1000000,1000000−1000000,1000000.
OutputFor 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
1 #include <iostream> 2 //#include<bits/stdc++.h> 3 #include <stack> 4 #include <queue> 5 #include <map> 6 #include <set> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <math.h> 11 using namespace std; 12 typedef long long LL; 13 typedef unsigned long long ull; 14 const int MAX=1e6+5; 15 int t,n,m; 16 int a[MAX],b[10005],f[MAX]; 17 int main() 18 { 19 scanf("%d",&t); 20 while(t--) 21 { 22 scanf("%d%d",&n,&m); 23 int i,j; 24 for(i=1;i<=n;i++) 25 scanf("%d",&a[i]); 26 for(i=1;i<=m;i++) 27 scanf("%d",&b[i]); 28 f[0]=f[1]=0; 29 for(i=2,j=0;i<=m;i++) 30 { 31 while(j&&b[j+1]!=b[i]) 32 { 33 j=f[j]; 34 } 35 if(b[j+1]==b[i]) 36 j++; 37 f[i]=j; 38 } 39 for(i=1,j=0;i<=n;i++) 40 { 41 while(j>0&&a[i]!=b[j+1]) 42 j=f[j]; 43 if(a[i]==b[j+1]) 44 { 45 j++; 46 } 47 48 if(j>=m) 49 { 50 break; 51 } 52 } 53 if(i<=n) 54 printf("%d ",i-m+1); 55 else 56 printf("-1 "); 57 58 } 59 }