首页 > 代码库 > HDU - 2087 剪花布条 （KMP）
HDU - 2087 剪花布条 （KMP）
Description
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Input
输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3 思路：KMP的一点改动而已，每次匹配到了重头再开始#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1010; char a[maxn], b[maxn]; int next[maxn]; void getfail(char *p) { int m = strlen(p); next[0] = 0, next[1] = 0; for (int i = 1; i < m; i++) { int j = next[i]; while (j && p[i] != p[j]) j = next[j]; next[i+1] = p[i] == p[j] ? j+1 : 0; } } int kmp() { int ans = 0; int n = strlen(a), m = strlen(b); int j = 0; for (int i = 0; i < n; i++) { while (j && b[j] != a[i]) j = next[j]; if (b[j] == a[i]) j++; if (j == m) { ans++; j = 0; } } return ans; } int main() { while (scanf("%s", a) != EOF && a[0] != '#') { scanf("%s", b); getfail(b); int ans = kmp(); printf("%d\n", ans); } return 0; }
HDU - 2087 剪花布条 （KMP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。