http://acm.hdu.edu.cn/showproblem.php?pid=1711
1 #include<stdio.h>
2 int a[1000001],b[10001],hh[10001]={0};
3 int n,m;
4 void KMP()
5 {
6 int i;
7 for(i=1;i<m;i++)
8 if (b[i] == b[ hh[i-1] ])
9 hh[i] = hh[i-1] + 1;
10 else
11 hh[i] = (b[i] == b[0]);
12 }
13 int cmp()
14 {
15 int i=0,j=0;
16 while (i<n)
17 {
18 if (j==0 || a[i]==b[j])
19 {
20 if(a[i]==b[j])
21 j++;
22 i ++;
23 }
24 else
25 j = hh[j-1];
26 if(j==m)
27 return i-j+1;
28 }
29 return -1;
30 }
31 int main()
32 {
33 int T,i,j,K;
34 scanf("%d",&T);
35 while (T--)
36 {
37 scanf("%d%d",&n,&m);
38 for(i=0;i<n;i++)
39 scanf("%d",&a[i]);
40 for(i=0;i<m;i++)
41 scanf("%d",&b[i]);
42 KMP();
43 printf("%d\n",cmp());
44 }
45 }
posted on 2009-02-09 22:41
shǎ崽 閱讀(243)
評論(0) 編輯 收藏 引用