hdu_2087 剪花布条(kmp)
2024-10-12 21:59:22
剪花布条
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15228 Accepted Submission(s): 9646
Problem Description
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?
Input
输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数,如果一块都没有,那就老老实实输出0,每个结果之间应换行。
Sample Input
abcde a3
aaaaaa aa
#
aaaaaa aa
#
Sample Output
0
3
3
Author
qianneng
简单的kmp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
char a[N],b[N];
int Next[N];
int kmp(char *a,char *b)
{
int len1 = strlen(a);
int len2 = strlen(b);
//求Next
int j = ;
int tm = Next[] = -;
while(j<len2-){
if(tm<||b[j]==b[tm]) {
Next[++j] = ++tm;
}
else tm = Next[tm];
}
/* for(int i = 0; i < len2; i++)
printf("%d ",Next[i]);
puts("");
*/
//匹配
int i;
int ans = ;
for(i = j = ; i < len1; ){
if(j==len2) {ans++; i--;j= -;}
if(j<||a[i]==b[j]) i++,j++;
else j = Next[j];
}
if(i==len1&&j==len2) ans++;
return ans;
}
int main()
{
while()
{
scanf("%s",a);
if(a[]=='#') return ;
getchar();
scanf("%s",b);
int ans = kmp(a,b); // puts("haha");
printf("%d\n",ans);
}
return ;
}
最新文章
- 【MySQL】函数IFNULL、设置默认时间
- Java学习笔记1
- Axure 使用心得总结
- css3 background
- tableFooterView中的按钮点击没反应
- Hadoop生态上几个技术的关系与区别:hive、pig、hbase 关系与区别
- BestCoder Round #71 (div.2) (hdu 5620 菲波那切数列变形)
- 删除浏览器浏览器删除cookie方法
- Logcat中报内存泄漏MemoryLeak的一次分析
- Visual Studio 2008项目中WinForm窗口图标显示为类图标,仅仅能打开代码而无法打开视图问题解决
- Tomcat的常用内置对象
- Objective-C RunTime 学习笔记 之 atomic/nonatomic 关键字
- HBase篇(1)-特性与应用场景
- ASP.NET AJAX入门系列(5):使用UpdatePanel控件(二) UpdatePanel
- [UE4]解决角色影子的问题
- Spring boot 错误处理机制
- 阿里云 CentOS 镜像和 EPEL 源
- How TCP clients and servers communicate using the TCP sockets interface
- 洛谷3778 [APIO2017]商旅
- 多线程 NSOpeartion 的使用