hdu2087 剪花布条--KMP-白红宇的个人博客

hdu2087 剪花布条--KMP

发布日期：2021-10-03 20:31:48 浏览次数：5 分类：技术文章

本文共 1068 字，大约阅读时间需要 3 分钟。

原题链接：

一：原题内容

Problem Description

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

Input

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

Output

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

Sample Input

abcde a3aaaaaa  aa#

Sample Output

二：分析理解

就是求模式串在主串出现的次数，easy！直接上代码。

三：AC代码

#include
   
    #include
    
     using namespace std;char s[1010];char p[1010];int nextval[1010];void GetNextval(){	int p_len = strlen(p);	int i = 0, j = -1;	nextval[0] = -1;	while (i < p_len)	{		if (j == -1 || p[i] == p[j])		{			i++;			j++;			if (p[i] != p[j])				nextval[i] = j;			else				nextval[i] = nextval[j];		}		else			j = nextval[j];	}}int KMP(){	GetNextval();	int s_len = strlen(s);	int p_len = strlen(p);	int ans = 0;	int i = 0, j = 0;	while (i < s_len)	{		if (j == -1 || s[i] == p[j])		{			i++;			j++;		}		else			j = nextval[j];		if (j == p_len)		{			j = 0;			ans++;		}	}	return ans;}int main(){	while (scanf("%s", s) && s[0] != '#'&&scanf("%s", p))	{		printf("%d\n", KMP());	}	return 0;}

转载地址：https://blog.csdn.net/LaoJiu_/article/details/50930492 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu3336 Count the string--KMP+DP

下一篇：hdu1358 Period--KMP

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章