http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
#include<stdio.h>
int a[10010],b[1000100],n,m,next[10010];
void getnext() {
int j=0,k=-1;
next[0]=-1;
while(j<m) {
if(k==-1||a[j]==a[k]) {
j++;k++;
if(a[j]!=a[k])
next[j]=k;
else
next[j]=next[k];
}
else k=next[k];
}
}
int kmp() {
int i=0,j=0,index=0;
while(i<n&&j<m) {
if(b[i]==a[j]){
i++;j++;
}
else {
index+=j-next[j];
if(next[j]!=-1)
j=next[j];
else {
j=0;i++;
}
}
}
if(j==m)
return index+1;
return -1;
}
int main(){
int i,j,t;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&b[i]);
for(i=0;i<m;i++)
scanf("%d",&a[i]);
getnext();
printf("%d
",kmp());
}
return 0;
}