LP14363.cpp

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
using i64 = long long;
const int N = 5e6+10, K = 1e7+110, B = 131;
const i64 P = 1'00000'00000'000069;

namespace PSGT {
    #define Mid ((L+R) >> 1)
    int cnt[K], ls[K], rs[K], idx;

    int cpynode(int u) {
        ++idx;
        ls[idx] = ls[u];
        rs[idx] = rs[u];
        cnt[idx] = cnt[u]+1;
        return idx;
    }

    void add(int& u, i64 p, i64 L, i64 R) {
        u = cpynode(u);
        if (L == R) return;
        if (p <= Mid) add(ls[u], p, L, Mid);
        else add(rs[u], p, Mid+1, R);
    }

    int query(int u, i64 p, i64 L, i64 R) {
        if (L == R) return cnt[u];
        if (p <= Mid) return query(ls[u], p, L, Mid);
        else return query(rs[u], p, Mid+1, R);
    }
}

namespace ACAM {
    int tr[N][26], fail[N], rt[N], idx;
    // i64 val[N];
    vector<i64> val[N];

    vector<int> g[N];

    void insert(const string& s, i64 v) {
        int u = 0;
        for (char c: s) {
            int p = c - 'a';
            if (!tr[u][p]) tr[u][p] = ++idx;
            u = tr[u][p];
        }
        val[u].pb(v);
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                if (tr[u][i]) {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i] = tr[fail[u]][i];
            }
        }
        for (int i = 1; i <= idx; i++) g[fail[i]].pb(i);
    }

    void dfs(int u) {
        rt[u] = rt[fail[u]];
        for (i64 v: val[u]) PSGT::add(rt[u], v, 0, P-1);
        for (int to: g[u]) {
            dfs(to);
        }
    }

    int solve(const string& t1, const string& t2) {
        int p = t1.size()-1;
        while (t1[p] == t2[p]) p--;
        int u = 0, ans = 0;
        i64 h = 0;
        for (int i = 0; i < t1.size(); i++) {
            u = tr[u][t1[i] - 'a'];
            h = (h * B + t1[i] - t2[i] + P) % P;
            if (i >= p) ans += PSGT::query(rt[u], h, 0, P-1);
        }
        return ans;
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        assert(s1.size() == s2.size());
        i64 v = 0;
        for (int j = 0; j < s1.size(); j++) {
            v = (v * B + s1[j] - s2[j] + P) % P;
        }
        ACAM::insert(s1, v);
    }
    ACAM::build();
    ACAM::dfs(0);

    for (int i = 1; i <= q; i++) {
        string t1, t2;
        cin >> t1 >> t2;
        if (t1.size() != t2.size()) {
            cout << "0\n";
            continue;
        }
        cout << ACAM::solve(t1, t2) << '\n';
    }
    return 0;
}