HDU 2087 剪花布条（KMP算法）

超、凢脫俗 2024-02-17 21:12 55阅读 0赞

## 剪花布条 ##

Problem Description

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

Input

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

Output

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

Sample Input

abcde a3
    aaaaaa  aa
    #

Sample Output

0
    3

分析：KMP算法模板题， 关于kmp算法，这篇博文写的通俗易懂： http://www.cnblogs.com/c-cloud/p/3224788.html

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1000+10;
    int next[maxn];
    char s1[maxn],s2[maxn];
    
    void get_next(){
    	int len=strlen(s2);
    	next[0]=0;
    	int k=0;
    	for(int p=1;p<len;p++){
    		 
    		while(k>0 && s2[k]!=s2[p]){
    			k=next[k-1];
    		}
    		
    		if(s2[k]==s2[p])k++;
    		
    		next[p]=k;
    	}
    }
    
    int main(){
    	while(scanf("%s",s1)==1 && s1[0]!='#'){
    		scanf("%s",s2);
    		
    		int len1=strlen(s1);
    		int len2=strlen(s2);
    		int i=0,j=0;
    		int cnt=0;
    		while(j<len1){
    			if(s2[i]==s1[j]){
    				i++;j++;
    			}
    			else if(i==0){
    				j++;
    			}
    			else {
    				i=next[i-1];
    			}
    			
    			if(i==len2){
    				cnt++;
    				i=0;
    			}
    		}
    		
    		printf("%d\n",cnt);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2087 剪花布条（KMP算法）

剪花布条 Problem Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从

超、凢脫俗/ 2024年02月17日 21:12/ 0 赞/ 56 阅读

相关 HDU 2087 剪花布条

kmp板题 kmp的主要过程： 1. 获得next数组 2. 生成next数组的过程，其实就是可以看做模式串自己和自己进行匹配，找出所有子串的前后缀子串集合中的最长公共

电玩女神/ 2022年12月18日 02:53/ 0 赞/ 144 阅读

相关 HDU 2087-剪花布条

[HDU 2087][] KMP算法 include<stdio.h> include<string.h> include<algorithm

灰太狼/ 2022年09月22日 13:52/ 0 赞/ 140 阅读

相关 HDU 2087 剪花布条 //简单kmp

剪花布条 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

桃扇骨/ 2022年08月23日 11:54/ 0 赞/ 149 阅读

相关 hdu2087剪花布条（kmp）

剪花布条 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

朱雀/ 2022年08月21日 08:59/ 0 赞/ 150 阅读

相关 HDU 2087剪花布条

原题地址：[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.ph

骑猪看日落/ 2022年08月05日 15:08/ 0 赞/ 136 阅读

相关 hdu 2087 剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

朱雀/ 2022年05月30日 20:39/ 0 赞/ 149 阅读

相关 Hdu 2087 剪花布条(KMP基础)

[传送门][Link 1] 题意：给你两个字符串问你其中一个字符串在另一个字符串中出现了几次。分析：这题显然用KMP做，不然很容易超时，其实这基本算是一个KMP模板题，如

谁践踏了优雅/ 2022年05月19日 06:58/ 0 赞/ 164 阅读

相关 HDU 2087 剪花布条 KMP入门

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

青旅半醒/ 2022年03月30日 04:58/ 0 赞/ 198 阅读

相关 hdu 2087 剪花布条 KMP

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.ph

小灰灰/ 2021年12月09日 15:41/ 0 赞/ 228 阅读