随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(235) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理