这是一道基础的kmp的题目。做法就不细说了。

对于kmp的知识,有篇博客介绍得非常全面——从头到尾彻底理解KMP(2014年8月4日版)

#include

int n,m,next[10000],s[1000000],p[10000];

void getnext()

{

int k=0,j=1;

next[0]=-1;next[1]=0;

while (j

{

if (k==-1||p[j]==p[k])

{

k++;

j++;

next[j]=k;

}

else k=next[k];

}

}

int kmp()

{

int i=0;

int j=0;

while (i

{

if (s[i]!=p[j]) while (s[i]!=p[j]) i++;

else

{

while (j!=-1&&j

{

if (s[i]==p[j])

{

i++;

j++;

if (j==m) break;

}

else j=next[j];

}

if (j==-1) j++;

}

}

if (j==m)

return i-j+1;

else

return -1;

}

int main()

{

int t,i;

scanf("%d",&t);

while (t--)

{

scanf("%d%d",&n,&m);

for (i=0;i

for (i=0;i

getnext();

printf("%d\n",kmp());

}

}

推荐链接

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。