1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000005
char s1[N], s2[N/100];
int next[N];
int main() {
    int T, i, j, l1, l2;
    scanf("%d", &T);
    while (T--) {
        scanf("%s%s", s2, s1);
        l1 = strlen(s1), l2 = strlen(s2);
        next[0] = -1;
        i = 0, j = -1;
        while (i < l2) {
            if (j == -1 || s2[i] == s2[j])
                next[++i] = ++j;
            else j = next[j];
        }
        long long ans = 0;
        i = j = 0;
        while (i < l1 && j < l2) {
            if (j < 0 || s1[i] == s2[j]) {
                i++, j++;
                if (j == l2) {
                    ans++, i--, j = next[j-1];
                }
            }else {
                j = next[j];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX