HDU 2087 剪花布条

剪花布条

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

Problem Description

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

Input

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

Output

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

Sample Input

abcde a3 aaaaaa aa #

Sample Output

0 3

Author

qianneng

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 int n;
 7 char a[1005];
 8 char b[1005];
 9 int nxt[1005];
10 int la, lb;
11 void get_nxt()
12 {
13     int i = 0;
14     int j = -1;
15     nxt[0] = -1;
16     while (i < lb)
17     {
18         if (j == -1 || b[i] == b[j]) nxt[++i] = ++j;
19         else j = nxt[j];
20     }
21 }
22 int main()
23 {
24     while (cin >> a)
25     {
26         if (a[0] == '#') break;
27         else cin >> b;
28         la = strlen(a);
29         lb = strlen(b);
30         get_nxt();
31         int i = 0, j = 0;
32         int s = 0;
33         while (i < la)
34         {
35             if (j == -1 || a[i] == b[j])
36             {
37                 i++;
38                 j++;
39             }
40             else j = nxt[j];
41             if (j == lb)
42             {
43                 s++;
44                 j = 0;//不是j=nxt[j],因为不能重复
45             }
46         }
47         cout << s << endl;
48     }
49     return 0;
50 }