HDU - 1711 Number Sequence

 1 #include<stdio.h>
 2 const int maxn=1000000+10,maxm=10000+5;
 3 int a[maxn],b[maxm],next[maxm];
 4 void get_next(int m)
 5 {
 6     int i=1,j=0;
 7     next[1]=0;
 8     while(i<m){
 9         if(j==0 || b[i]==b[j]) {i++;j++;next[i]=j;}
10         else j=next[j];
11     }
12 }
13 int get_index(int n,int m)
14 {
15     int i=1,j=1;
16     while(i<=n && j<=m){
17         if(j==0 || a[i]==b[j]){
18             i++;
19             j++;
20         }
21         else
22             j=next[j];
23     }
24     if(j>m)
25         return i-m;
26     else
27         return -1;
28 }
29 int main()
30 {
31     int t;
32     scanf("%d",&t);
33     while(t--){
34         int n,m;
35         scanf("%d%d",&n,&m);
36         for(int i=1;i<=n;i++)
37             scanf("%d",&a[i]);
38         for(int i=1;i<=m;i++)
39             scanf("%d",&b[i]);
40         get_next(m);
41         int ans=get_index(n,m);
42         printf("%d\n",ans);
43     }
44     return 0;
45 }