HDU

 1 #include <iostream>
 2 #include <cstring>
 3 #define MAXSIZE 1010
 4 using namespace std;
 5 
 6 char a[MAXSIZE];
 7 char b[MAXSIZE];
 8 char Next[MAXSIZE];
 9 int Len_a, Len_b;
10 int sum;
11 
12 void GetNext()
13 {
14     int i = 0;
15     int j = Next[0] = -1;
16     while (i < Len_b)
17     {
18         if (j < 0 || b[i] == b[j])
19         {
20             i++;
21             j++;
22             Next[i] = (b[i] == b[j] ? Next[j] : j);
23         }
24         else
25             j = Next[j];
26     }
27 }
28 
29 void KMP()
30 {
31     int i = 0, j = 0;
32     while (i < Len_a)
33     {
34         if (j < 0 || a[i] == b[j])
35         {
36             i++;
37             j++;
38             if (j == Len_b)
39             {
40                 sum++;
41                 j = 0;
42             }
43         }
44         else
45             j = Next[j];
46     }
47 }
48 
49 int main(void)
50 {
51     ios::sync_with_stdio(false);
52     while (true)
53     {
54         sum = 0;
55         cin >> a;
56         if (a[0] == '#')
57             break;
58         cin >> b;
59 
60         Len_a = strlen(a);
61         Len_b = strlen(b);
62         GetNext();
63         KMP();
64         cout << sum << endl;
65     }
66 
67     return 0;
68 }