hdu1711Number Sequence（KMP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1711

KMP模板题。

一篇很不错的关于KMP的讲解，认真看完可以掌握KMP，但是nex数组和平时用的不太一样（不建议用这个）。

 1 #include<cstdio>
 2 #include<cstring>
 3 int t[1001010],p[10010];
 4 int nex[10010];
 5 int  n,m;
 6 void getnex()
 7 {
 8     int j=0,k=-1;
 9     nex[0]=-1;
10     while(j<m)
11         if(k==-1||p[j]==p[k])
12             nex[++j]=++k;
13         else k=nex[k];
14 }
15 
16 int KMP(int *s,int *p)
17 {
18     int i=0,j=0;
19     while(i<n&&j<m)
20     {
21         if(j==-1||s[i]==p[j])
22         {
23             i++;
24             j++;
25         }
26         else j=nex[j];
27     }
28 
29     if(j==m) return i-m+1;
30     else return -1;
31 }
32 
33 int main()
34 {
35     int tt;
36     scanf("%d",&tt);
37     while(tt--)
38     {
39 
40         scanf("%d%d",&n,&m);
41        for(int i=0;i<n;i++)
42         scanf("%d",&t[i]);
43        for(int i=0;i<m;i++)
44         scanf("%d",&p[i]);
45         getnex();
46         int pos=KMP(t,p);
47         printf("%d
",pos);
48     }
49     return 0;
50 }

刚知道有一个函数：strstr（）很好用，有需要请自行百度。