HDU 1717

KMP模板题、
直接放代码
 1 #include<cstdio>
 2 #include<cstring>
 3 const int qq=1e6+10;
 4 int next[qq];
 5 int x[qq],y[qq];
 6 int n,m;
 7 int KMP()
 8 {
 9     int i,j;
10     i=j=0;
11     while(i<n){
12         if(j==-1||x[i]==y[j]){
13             ++i;++j;
14         }
15         else
16             j=next[j];
17         if(j==m)
18             return i-m+1;
19     }
20     return -1;     
21 }
22 int main()
23 {
24     int t;scanf("%d",&t);
25     while(t--){
26         scanf("%d%d",&n,&m);
27         for(int k=0;k<n;++k)
28             scanf("%d",&x[k]);
29         for(int k=0;k<m;++k)
30             scanf("%d",&y[k]);
31         int i,j;
32         next[0]=-1;
33         i=0;j=-1;
34         while(i<m){
35             if(j==-1||y[i]==y[j]){
36                 ++i;++j;
37                 next[i]=j;
38             }
39             else
40                 j=next[j];
41         }
42         int ans=KMP();
43         if(ans!=-1)    printf("%d
",ans);
44         else    printf("-1
");
45     }
46     return 0;
47 }