解题思路：

本题要求统计一个单词W在长文本$T$中的出现次数，允许重叠。由于W和T的长度可能很大（$W$最长$1e4$，$T$最长$1e6$），直接暴力匹配会导致超时。因此采用滚动哈希（$Rabin-Karp$算法）优化匹配过程。

关键步骤：

1.哈希预处理

预计算哈希基数$P$的幂次数组$xp$，用于快速计算子串哈希值。 对文本$T$计算前缀哈希数组$h$，使得任意子串的哈希值可通过前缀哈希快速计算。

2.哈希匹配

计算模式串$W$的哈希值$q$。 遍历$T$的所有可能起始位置，计算对应子串的哈希值并与$q$比较，若相等则计数加一。

C++实现：

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int N = 1e6 + 14, P = 131; // 定义最大长度和哈希基数
char s1[N], s2[N];              // 存储模式串W和文本T
ull xp[N], h[N];                // xp存储P的幂次，h存储前缀哈希值

// 计算区间[l, r]的哈希值
ull get(int l, int r) {
    return h[r] - h[l - 1] * xp[r - l + 1];
}

int main() {
    // 预处理P的幂次，xp[i] = P^i
    xp[0] = 1;
    for (int i = 1; i < N; i++) xp[i] = xp[i - 1] * P;

    int kase;
    cin >> kase; // 读取测试用例数量

    while (kase--) {
        // 输入模式串W和文本T，下标从1开始存储
        cin >> s1 + 1 >> s2 + 1;
        int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1), cnt = 0;
        memset(h, 0, sizeof h); // 重置前缀哈希数组

        // 计算模式串W的哈希值q
        ull q = 0;
        for (int i = 1; i <= len1; i++) q = q * P + s1[i];

        // 计算文本T的前缀哈希数组h
        for (int i = 1; i <= len2; i++) h[i] = h[i - 1] * P + s2[i];

        // 遍历所有可能的起始位置，比较哈希值
        for (int i = 1; (i + len1 - 1) <= len2; i++)
            if (get(i, i + len1 - 1) == q) cnt++; // 哈希匹配则计数
        cout << cnt << endl; // 输出结果
    }
    return 0;
}