贴代码,觉得带template的有一些大材小用……不过还是按自己风格写吧！
/*******************************************************************************/
/* OS : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
* Compiler : g++ (GCC) 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
* Encoding : UTF8
* Date : 2014-04-26
* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> using namespace std;
template<typename S,typename T>
void get_nextval(S const * ptrn,T plen,T *nextval){ T i=; //i从0开始
nextval[i]=-;
T j=-;
while(i<plen){ if(j==-||ptrn[i]==ptrn[j]){
++i;
++j;
//if(ptrn[i]!=ptrn[j]){
nextval[i]=j;
// }else nextval[i]=nextval[j]; }else j=nextval[j];
}
}
template<typename S,typename T>
T kmp_search(S const * src,T slen,S const *ptrn,T plen,T const *nextval,T pos){ T i=pos,j=;
while(i<slen)
{
if(src[i]==ptrn[j])
{
if(j==plen-) return i-(plen-)+;
i++;j++;
}
else
{
j=nextval[j];
if(j==-) {i++;j=;}
}
}
return -; }
int src[],ptrn[];
int nextval[];
int main(){ int T,slen,plen,i;
scanf("%d",&T);
while(T--){ scanf("%d%d",&slen,&plen);
for(i=;i<slen;i++){
scanf("%d",src+i); }
for(i=;i<plen;i++){ scanf("%d",ptrn+i);
} get_nextval(ptrn, plen, nextval); printf("%d\n",kmp_search(src, slen, ptrn, plen, nextval, )); } return ; }