Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

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

Input

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

Output

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

Sample Input

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;
}

 

分类: ACM/ICPC

发表评论

电子邮件地址不会被公开。 必填项已用*标注