HDU 2087 剪花布条解题报告

HDU 2087 剪花布条解题报告

dianlujitao 无回复

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

Description

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

Input

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

Output

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

Sample Input

abcde a3
aaaaaa  aa
#

abcde a3

aaaaaa aa

Sample Output

0
3

Source

冬练三九之二

KMP求主串中匹配到模式串的个数，不可重叠

AC代码：

#include <cstdio>
#include <cstring>
using namespace std;
char a[1010], b[1010];
void kmp_pre(char x[], int m, int next[])
{
	int i, j;
	j = next[0] = -1;
	i = 0;
	while (i < m)
	{
		while (-1 != j && x[i] != x[j])
			j = next[j];
		next[++i] = ++j;
	}
}
int next[1010];
int kmp_count(char x[], int m, char y[], int n)
{
	int i, j;
	int ans = 0;
	kmp_pre(x, m, next);
	i = j = 0;
	while (i < n)
	{
		while (-1 != j && y[i] != x[j])
			j = next[j];
		i++, j++;
		if (j >= m)
		{
			ans++;
			j = 0;
		}
	}
	return ans;
}
int main()
{
	while (scanf("%s%s\n", a, b) == 2)
		printf("%d\n", kmp_count(b, strlen(b), a, strlen(a)));
	return 0;
}

#include <cstdio>

#include <cstring>

using namespace std;

char a[1010], b[1010];

void kmp_pre(char x[], int m, int next[])

{

int i, j;

j = next[0] = -1;

i = 0;

while (i < m)

{

while (-1 != j && x[i] != x[j])

j = next[j];

next[++i] = ++j;

}

int next[1010];

int kmp_count(char x[], int m, char y[], int n)

{

int i, j;

int ans = 0;

kmp_pre(x, m, next);

i = j = 0;

while (i < n)

{

while (-1 != j && y[i] != x[j])

j = next[j];

i++, j++;

if (j >= m)

{

ans++;

j = 0;

}

return ans;

}

int main()

{

while (scanf("%s%s\n", a, b) == 2)

printf("%d\n", kmp_count(b, strlen(b), a, strlen(a)));

return 0;

}

Dianlujitao's Space

HDU 2087 剪花布条解题报告

来一发吐槽撤销评论

来一发吐槽 撤销评论

来一发吐槽撤销评论