HDU 2087 剪花布条 解题报告
dianlujitao
无回复
Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?
Input
输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数,如果一块都没有,那就老老实实输出0,每个结果之间应换行。
Sample Input
1 2 3 |
abcde a3 aaaaaa aa # |
Sample Output
1 2 |
0 3 |
Source
KMP求主串中匹配到模式串的个数,不可重叠
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#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; } |
来一发吐槽