将 $[A]$ 所有串的哈希值放入集合，然后对 $B$ 中所有长为 $|A|$ 的串求哈希值，如果在集合中答案加 $1$。

#include <iostream>
#include <map>
#include <set>
#include <string>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, B = 131;

ull p[N], h1[N], h2[N];
ull get(ull h[], int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
void solve() {
    string a, b; cin >> a >> b;
    int n = a.size(), ans = 0;
    a = ' ' + a + a;
    b = ' ' + b;

    p[0] = 1, h1[0] = h2[0] = 0;
    for (int i = 1; i < max(a.size(), b.size()); i++) {
        p[i] = p[i - 1] * B;
        if (i < a.size()) h1[i] = h1[i - 1] * B + a[i];
        if (i < b.size()) h2[i] = h2[i - 1] * B + b[i];
    }
    set<ull> st;
    for (int i = 1; i + n - 1 < a.size(); i++)
        st.insert(get(h1, i, i + n - 1));
    for (int i = 1; i + n - 1 < b.size(); i++)
        ans += st.count(get(h2, i, i + n - 1));
    cout << ans << '\n';
}
int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T; while (T--) solve();
    return 0;
}