剪花布条

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11544 Accepted Submission(s): 7421

Problem Description

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

Input

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

Output

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

Sample Input

abcde a3
aaaaaa  aa
#

Sample Output

0
3

数据好水，KMP样例不过题直接过

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 
13 using namespace std;
14 
15 const int maxn = 1010;
16 int na, nb;
17 char a[maxn];
18 char b[maxn];
19 int pre[maxn];
20 
21 //b是模式串，a是目标串
22 void getpre(char *b, int *pre) {
23     int j, k;
24     pre[0] = -1;
25     j = 0;
26     k = -1;
27     while(j < nb) {
28         if(k == -1 || b[j] == b[k]) {
29             j++;
30             k++;
31             pre[j] = k;
32         }
33         else {
34             k = pre[k];
35         }
36     }
37 }
38 
39 int kmp() {
40     int ans = 0;
41     int i = 0;
42     int j = 0;
43     getpre(b, pre);
44     while(i < na) {
45         if(j == -1 || a[i] == b[j]) {
46             i++;
47             j++;
48         }
49         else {
50             j = pre[j];
51         }
52         if(j == nb) {
53             ans++;
54         }
55         if(i == na) {
56             return ans;
57         }
58     }
59 }
60 
61 int main() {
62     // freopen("in", "r", stdin);
63     while(scanf("%s", a) && strcmp(a, "#") != 0) {
64         scanf("%s", b);
65         na = strlen(a);
66         nb = strlen(b);
67         getpre(b, pre);
68         printf("%d
", kmp());
69     }
70 }