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;}