HDU-1686 Oulipo

t组数据求模式串在文本串中的出现次数（允许重叠）
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 const int maxm = 1e4 + 10;
 8 const int maxn = 1e6 + 10;
 9 char P[maxm], T[maxn];
10 int f[maxm];
11 
12 int Tc, N, M;
13 int ans;
14 
15 void getFail(char* p, int *f) {
16     f[0] = 0;
17     f[1] = 0;
18     for (int i = 1; i < M; i++) {
19         int j = f[i];
20         while (j && P[i] != P[j]) j = f[j];
21         f[i + 1] = P[i] == P[j] ? j + 1 : 0;
22     }
23 }
24 
25 void find(char* T, char* P, int* f) {
26     int j = 0;
27     for (int i = 0; i < N; i++) {
28         while (j && P[j] != T[i]) j = f[j];
29         if (P[j] == T[i]) j++;
30         if (j == M) {
31             ans++;
32             if (j != 1) {
33                 i--;
34                 j--;
35                 j = f[j];    
36             }
37             
38         }
39     }
40 }
41 
42 int main() {
43     scanf("%d", &Tc);
44     while (Tc--) {
45         ans = 0;
46         scanf("%s", P);
47         scanf("%s", T);
48         N = strlen(T);
49         M = strlen(P);
50         getFail(P, f);
51         find(T, P, f);
52         printf("%d
", ans);
53     }
54 
55     return 0;
56 }