hdu2087剪花布条[KMP]

本文主要是介绍hdu2087剪花布条[KMP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剪花布条

TimeLimit: 1000/1000 MS (Java/Others)    Memory Limit:32768/32768 K (Java/Others)
Total Submission(s):16662    Accepted Submission(s): 10565

Problem Description

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

 

 

Input

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。

 

 

Output

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

 

 

Sample Input

abcde a3

aaaaaa aa

#

 

 

Sample Output

0

3

 

传说中的模板题，没什么好说的。

还有就是建议学算法先弄清楚模板以后再写模板题，以免养成不好的编程习惯导致程序不好调；

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e3+5;
int len,len2,nxt[maxn],ans;
char tmp1[maxn],tmp2[maxn];
void init()
{len=strlen(tmp2);nxt[0]=-1;nxt[1]=0;for(inti=2;i<len;i++){intcnt=i-1;while(nxt[cnt]&&tmp2[nxt[cnt]+1]!=tmp2[i])cnt=nxt[cnt];if(nxt[cnt])nxt[i]=nxt[cnt]+1;elsenxt[i]=0;}
}
int main()
{freopen("hdu2087.in","r",stdin);freopen("hdu2087.out","w",stdout);for(scanf("%s",&tmp1);tmp1[0]!='#';scanf("%s",&tmp1)){scanf("%s",&tmp2);ans=0;init();len2=strlen(tmp1);intj=-1;for(inti=0;i<len2;i++){j++;while(tmp1[i]!=tmp2[j]&&j!=-1)j=nxt[j];if(j==len-1){ans++;j=-1;}}printf("%d\n",ans);}return0;
}

用后来我用得比较熟练的模板重写了一次：感觉这个模板要便于理解一点。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int len1,len2,ans,nxt[1005];
char a[1005],b[1005];
int main()
{
freopen("hdu2087.in","r",stdin);
freopen("hdu2087.out","w",stdout);
for(scanf("%s",a);a[0]!='#';scanf("%s",a)){
scanf("%s",b);
nxt[0]=-1;nxt[1]=0;ans=0;
len1=strlen(a);len2=strlen(b);
for(int i=2;i<=len2;i++){
int j=i-1;
while(b[i-1]!=b[nxt[j]]&&j)j=nxt[j];
nxt[i]=nxt[j]+1;
}
int cnt=0;
for(int i=0;i<len1;i++){
while(a[i]!=b[cnt]&&cnt>0)cnt=nxt[cnt-1];
if(a[i]==b[cnt])cnt++;
if(cnt==len2){
ans++;cnt=0;
}
}
printf("%d\n",ans);
}
return 0;
}

这篇关于hdu2087剪花布条[KMP]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---