很容易想到一个 $n^3$ 的做法。

即一层暴力移位，一层暴力 $B$ ，一层 $check$ 。

哈希字符串 $A$ ，$check$ 层降为 $O(1)$ 。哈希预处理 $n$ 个 $A(K)$ ，丢到 $map$ 里单次查询降为 $O(log)$ 。

#include <bits/stdc++.h>

using i64 = long long;

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;

constexpr int mod = 1E9 + 7;

template <class T>
struct Hash {
    const int N;
    const ull P = 13331;
    std::vector<T> p, S;
    Hash(int _) : N(_), p(_ + 1), S(_ + 1) {}
    Hash(std::string s) : Hash(int(s.size())) {
        p[0] = 1;
        for (int i = 1; i <= N; ++i) {
            p[i] = p[i - 1] * P;
        }
        for (int i = 1; i <= N; ++i) {
            S[i] = S[i - 1] * P + 1ull * s[i - 1];
        }
    }

    T get_sub(int l, int r) {
        return S[r] - S[l - 1] * p[r - l + 1];
    }
};

void solve() {
    std::string A, B;
    std::cin >> A >> B;

    Hash<ull> hasb(B), hasa(A);

    const int n = int(A.size()), lenb = int(B.size());
    std::map<ull, bool> map;
    map.emplace(hasa.get_sub(1, n), true);
    for (int l = n, r = n; l > 1; --l) {
        auto t = hasa.get_sub(l, r);
        map.emplace(t * hasa.p[l - 1] + hasa.S[l - 1], true);
    }

    int ans = 0;
    for (int i = 0; i + n - 1 < lenb; ++i) {
        ans += map.count(hasb.get_sub(i + 1, i + n));
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}