KMP(匹配)
2024-09-24 19:46:43
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; char a[],b[];
int fail[];
int la,lb;
void KMP(); int main()
{
while(scanf("%s",a+),a[]!='#')//输入从1号位置开始
{
la=strlen(a+);
scanf("%s",b+);
lb=strlen(b+);
//cout<<la<<lb<<endl;
KMP();
}
return ;
}
void KMP()
{
memset(fail,,sizeof(fail));
fail[]=-;
for(int i=;i<=lb;i++)
{
int p=fail[i-];
while(p>=&&b[p+]!=b[i])
p=fail[p];
fail[i]=p+;
}
int ans=;
for(int i=,p=;i<=la;i++)
{
while(p>=&&b[p+]!=a[i])
p=fail[p];
if(++p==lb)
{
ans++;
//为了防止出现重复匹配
p=fail[p]+p;
}
}
printf("%d\n",ans);
}
最新文章
- Package Configurations的使用示例
- error C2065: “CDatabase”: 未声明的标识符
- NuGet v3 feed带来的惊喜
- 23. Merge k Sorted Lists
- ADF_Starting系列5_使用ADF开发富Web应用程序之维护User Interface(Part2)
- ios开发错误笔记
- c_str 以及atoi
- 最简单的基于FFMPEG的音频编码器(PCM编码为AAC)
- tyvj 1934 高精度
- (C#)Windows Shell 外壳编程系列8 - 同后缀名不同图标?
- 上海赛趣-top.mainFrame.tabAddHandler方法详解
- Linuxc - 操作系统内存分配
- Trie树详解及其应用
- CentOS 7.x 如何关闭 numa
- memset memcmp memcpy memmove 自己实现
- 【XSY2701】异或图 线性基 容斥原理
- .netcore读取配置文件
- 10种JavaScript开发者必备的VS Code插件
- c __cplusplus详解
- 08 - JavaSE之IO流
热门文章
- C++学习笔记(六):复杂数据类型(string、容器和STL)
- WEB- 冻结TABLE的头和列
- [开心IT面试题] realloc用法
- 【UNIX】select、poll、epoll学习
- 获利能力分析COPA的BAPI:BAPI_COPAACTUALS_POSTCOSTDATA 通过增强返回凭证号
- 【转】安装Ubuntu 15.10后要做的事
- 删除浏览器浏览器删除cookie方法
- ORACLE 毫秒与日期的相互转换
- 生产者/消费者问题的多种Java实现方式--转
- 通过scrollerview自定义collectionview(常用于推荐关注界面)