31 char a[MAXN], b[MAXN];32 int sum;33 34 int* buildNext(char *P) {35     size_t m = strlen(P), j = 0;36     int *N = new int[m];37     int t = N[0] = -1;38     while (j < m - 1) {39         if (0 > t || P[j] == P[t]) j++, t++, N[j] = t;40         else t = N[t];41     }42     return N;43 }44 45 void match(char *P, char *T) {46     int *next = buildNext(P);47     int n = strlen(T), i = 0;48     int m = strlen(P), j = 0;49     while (i < n) {    50         if (0 > j || T[i] == P[j]) {51             if (j == m - 1) {52                 j = next[j], sum++;53                 continue;54             }55             i++, j++;56         }57         else j = next[j];58     }59     delete[] next;60 }61 62 int main() {63     int T;64     cin >> T;65     while (T--) {66         sum = 0;67         scanf("%s%s", a, b);68         match(a, b);69         cout << sum << endl;70     }71     return 0;72 }