剪花布条 HDU - 2087(kmp,求不重叠匹配个数)
2024-08-31 13:40:35
Problem Description
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?
Input
输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数,如果一块都没有,那就老老实实输出0,每个结果之间应换行。
Sample Input
abcde a3
aaaaaa aa
#
Sample Output
0
3
这是一道简单题有很多种做法在这只介绍kmp这种方法。
操作代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxx 1010
char a[maxx],b[maxx];
int p[maxx],n,m;
void pre()//求p[]数组;
{
p[]=;
int j=;
for(int i=;i<m;i++)
{
while(j>&&b[j+]!=b[i+])
j=p[j];
if(b[j+]==b[i+])
j++;
p[i+]=j;
}
}
int kmp()//匹配过程
{
int ans=,j=;
for(int i=;i<n;i++)
{
while(j>&&b[j+]!=a[i+])
j=p[j];
if(b[j+]==a[i+])
j++;
if(j==m)
{
ans++;
j=;//从头开始匹配,保证不重叠;
}
}
return ans; }
int main()
{
while(cin>>a+)//a+1表示读入的字符串串首为a[1];
{
if(a[]=='#')break;
cin>>b+;
m=strlen(b+);
n=strlen(a+);
pre();
cout<<kmp()<<endl;
}
return ;
}
下面来一道求重叠部分的题目
Oulipo POJ - 3461(kmp,求重叠匹配个数)
最新文章
- problem-eclipse创建maven项目报错
- C#-WinForm-MDI窗体容器、权限设置
- dandelion datatables : Page index must not be less than zero!
- 自制jquery可编辑的下拉框
- [Linux] yum和apt-get用法及区别
- iOS耳机操作
- 开发工具IDEA的使用
- JNI 从C文件向Java文件传递多个参数
- html的空格显示距离问题
- (大数据工程师学习路径)第四步 SQL基础课程----修改和删除
- android中自定义shape
- python基础(二)- 字符串
- 常见Android面试题及答案(详细整理)
- 201521123044 《Java程序设计》第13周学习总结
- [自用]多项式类数学相关(定理&;证明&;板子)
- mysql 合并left join 数据条目
- leetcode刷题笔记231 2的幂
- git bash 支持中文
- js工具库---Lodash
- python模块:json