http://acm.hdu.edu.cn/showproblem.php?pid=1711
做了KMP，感觉有点不懂为什么要next函数，最后问了涛神，懂了，原来next是找出自己重复的子串，只要有重复的就直接移动过去就可以了，第一次做KMP一a，这是赤裸裸的模版的，水题
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n,m;
int a[1000002],b[1000002],next[1000002];
void getnext()
{
int i=1,j=0;
next[1]=0;
while(m>i)
{
if(j==0||b[i]==b[j])
{
++i;++j;
if(b[i]==b[j])
next[i]=next[j];
else
next[i]=j;
}
else
j=next[j];
}
}
int KMP()
{
int i=0,j=0;
while(n>=i&&m>=j)
{
if(j==0||a[i]==b[j])
{
++i;++j;
}
else
j=next[j];
}
if(j>m) return i-m;
else
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int j=1;j<=m;++j)
scanf("%d",&b[j]);
getnext();
printf("%d\n",KMP());
}
//system("pause");
return 0;
}