#include<bits/stdc++.h> using namespace std; const int MAXN=1005; int Next[MAXN]; char str[MAXN],pattern[MAXN]; int cnt; int getFail(char *p,int plen){ Next[0]=0,Next[1]=0; for(int i=1;i<plen;i++){ int j=Next[i]; while(j&&p[i]!=p[j]) j=Next[j]; Next[i+1]=(p[i]==p[j])?j+1:0; } } int kmp(char *s,char *p){ int last=-1; int slen=strlen(s),plen=strlen(p); getFail(p,plen); int j=0; for(int i=0;i<slen;i++){ while(j&&s[i]!=p[j])j=Next[j]; if(s[i]==p[j])j++; if(j==plen){ //printf("at location= %d, %s\n",i+1-plen,&s[i+1-plen]); if(i-last>=plen){ cnt++; last=i; } } } } int main(){ while(~scanf("%s",str)){ if(str[0]=='#') break; scanf("%s",pattern); cnt=0; kmp(str,pattern); cout<<cnt; } }
原文链接: https://www.cnblogs.com/LH2000/p/13170415.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/357250
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!