poj3641(KMP求子串重复次数)

题目链接：http://poj.org/problem?id=3461

题意：求字符串T在字符串W中出现的次数。

代码：

#include<stdio.h>#include<string.h>char W[100005];int next[100005];char T[1000005];int ans ;int lenW,lenT;void getnext(){int i,j;next[1]=0;    j=0;for(i=2;i<=lenW;i++){ while(j>0 && (W[j+1] - W[i] !=0) )  j=next[j];         if(W[j+1] == W[i])  j=j+1;         next[i]=j;}}void getans(){int i,j;j=0;ans = 0;    for(i=1;i<=lenT;i++)    {     while(j>0 && (W[j+1] != T[i]) ) j=next[j];     if(W[j+1] == T[i]) j=j+1;     if(j == lenW)     {ans++;j=next[j]; }}}int main(){int ncase;scanf("%d",&ncase);getchar();while(ncase--){memset(W,'\0',sizeof(W));memset(T,'\0',sizeof(T));        gets(W+1);gets(T+1);lenW = strlen(W+1);lenT = strlen(T+1);getnext();getans();printf("%d\n",ans);}return 0;}