题目链接:HDU 2087
Problem Description
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?
输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。
Output
输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。
Sample Output
Source
冬练三九之二
Solution
题意
如题。
思路
KMP 裸题,每次匹配成功后模式串指针指向模式串首就行了。
Code
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 43 44 45 46
| #include <bits/stdc++.h> using namespace std;
int pi[1010];
void prefix_function(string s) { memset(pi, 0, sizeof(pi)); for(int i = 1; i < s.size(); ++i) { int j = pi[i - 1]; while(j > 0 && s[i] != s[j]) j = pi[j - 1]; if(s[i] == s[j]) ++j; pi[i] = j; } }
int kmp(string t, string p) { prefix_function(p); int ans = 0; int i = 0, j = 0; while(i < t.size()) { if(t[i] == p[j]) { ++i; ++j; } else { if(j == 0) ++i; else j = pi[j - 1]; } if(j == p.size()) { ++ans; j = 0; } } return ans; }
int main() { ios::sync_with_stdio(false); cin.tie(0); string t, p; while(cin >> t) { if(t[0] == '#') break; cin >> p; cout << kmp(t, p) << endl; } return 0; }
|