Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 37980 Accepted Submission(s):
23204
http://acm.hdu.edu.cn/showproblem.php?pid=2087
#include<cstdio> #include<cstring> const int maxt=1000+3; int i,j,k; int next[maxt]; char w[maxt],t[maxt]; int main(){ while(scanf("%s",t)){ if(t[0]==‘#‘){ return 0; }else{ scanf("%s",w); int lenw=strlen(w); int lent=strlen(t); next[0]=-1; k=-1; j=0; while(j<lenw){ if(k==-1||w[j]==w[k]){ k++; j++; if(w[j]!=w[k]){ next[j]=k; }else{ next[j]=next[k]; } }else{ k=next[k]; } } int sum=0; i=0; j=0; while(i<lent){ // printf("!!!!!\n"); if(j==lenw-1&&w[j]==t[i]){ sum++; j=0; i++; }else{ if(j==-1||w[j]==t[i]){ j++; i++; }else{ j=next[j]; } } } printf("%d\n",sum); } } return 0; }
原文:https://www.cnblogs.com/qqshiacm/p/11519339.html