首页 > 代码库 > HDU 2087 剪花布条
HDU 2087 剪花布条
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2087
解题思路:
简单的kmp算法
实现代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=1010; void makeNext(const char P[],int next[]){ int m=strlen(P); int k; memset(next,0,sizeof(next)); for(int i=1,k=0;i<m;i++){ if(k>0&&P[k]!=P[i]) k=next[k-1]; if(P[k]==P[i]) k++; next[i]=k; } } int kmp(const char T[],const char P[],int next[]){ int ans=0; makeNext(P,next); int m=strlen(P); int n=strlen(T); for(int i=0,k=0;i<n;i++){ if(k>0&&P[k]!=T[i]) k=next[k-1]; if(P[k]==T[i]) k++; if(k==m){ ans++; k=0; } } return ans; } int main(){ char T[MAXN]; char P[MAXN]; int next[MAXN]; while(scanf("%s",T)!=EOF){ if(T[0]==‘#‘) break; scanf("%s",P); cout<<kmp(T,P,next)<<endl; } }
HDU 2087 剪花布条
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。