原题请点击此处 **Sample Input abcde a3 aaaaaa aa #
Sample Output 0 3 **
#include<stdio.h> #include<string.h> int Index_KMP(char S[],char T[],int next[]){ int i=0,j=0,k=0; int lenT,lenS; lenT=strlen(T); lenS=strlen(S); while(i<lenS) { if(j==-1||S[i]==T[j]){++i;++j;} else j=next[j]; if(j>lenT-1){ k++; } } return k; } void get_next(char T[],int next[]){ int i,j,lenT; i=0;next[0]=-1;j=-1; lenT=strlen(T); while(i<lenT-1) { if(j==-1||T[i]==T[j]) { ++i;++j;next[i]=j; } else j=next[j]; } } int main(){ int next[10005]; char S[1000005],T[10005]; int k; while(scanf("%s",S)){\ if(S[0]=='#') break; scanf("%s",T); get_next(T,next); k=Index_KMP(S,T,next); printf("%d\n",k); } return 0; }