思路与算法

把规则与询问的共同前后缀裁掉，精确差异核心二元组相同才可匹配。规则左公共缀必须是询问左缀的后缀，右公共缀必须是右缀的前缀；反向左Trie与正向右Trie把两个条件化为祖先区间。每规则成为二维Euler矩形，按核心分组离线扫描，树状数组区间加点查询计数。

正确性说明

询问两串不同，使首次差异强制规则首次差异的绝对对齐，故每规则至多一个位置。裁掉公共前后缀后，核心对必须完全相等；其外恰需左侧后缀、右侧前缀一致，且这两个条件充分。反向/正向前缀Trie中，规则节点是询问节点祖先当且仅当前缀条件成立，Euler将其变为子树区间。闭矩形加一、点查询按核心分组计所有规则及重数。每组的结束事件全部撤销，BIT不会跨组残留。

复杂度

令L=L1+L2，R=n+q。期望O(L+R log R+R log L)时间、O(L+R)空间；固定26字母的稀疏Trie边扫描为常数因子，含精确字符串分组、两Trie初始化/Euler遍历、事件排序和BIT初始化。

易错点

核心分组使用完整字符串键和精确相等判断，哈希冲突不影响正确性；规则相同仍分别计数，规则两串相同不能得到不同询问，长度不同直接0。不要枚举所有替换位置到平方级。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Trie {
    struct N {
        int head, tin, tout;
    };
    struct E {
        int v, next, ch;
    };
    vector<N> nodes;
    vector<E> edges;
    Trie(size_t reserveSize) {
        nodes.reserve(reserveSize + 1);
        edges.reserve(reserveSize);
        nodes.push_back({-1, 0, 0});
    }
    int insert(const string &s, bool rev) {
        int u = 0;
        for (int z = 0; z < (int)s.size(); z++) {
            int c = s[rev ? s.size() - 1 - z : z] - 'a', e = nodes[u].head;
            while (e >= 0 && edges[e].ch != c)
                e = edges[e].next;
            if (e < 0) {
                int v = nodes.size();
                nodes.push_back({-1, 0, 0});
                edges.push_back({v, nodes[u].head, c});
                nodes[u].head = edges.size() - 1;
                u = v;
            } else
                u = edges[e].v;
        }
        return u;
    }
    void build() {
        int timer = 0;
        vector<pair<int, bool>> st;
        st.push_back({0, false});
        while (!st.empty()) {
            auto p = st.back();
            st.pop_back();
            int u = p.first;
            if (p.second) {
                nodes[u].tout = timer;
                continue;
            }
            nodes[u].tin = ++timer;
            st.push_back({u, true});
            for (int e = nodes[u].head; e >= 0; e = edges[e].next)
                st.push_back({edges[e].v, false});
        }
    }
};
struct Rec {
    string left, right;
    int group, index, L, R;
};
struct Ev {
    int group, x, type, y, z, delta, id;
    bool operator<(const Ev &o) const {
        return tie(group, x, type) < tie(o.group, o.x, o.type);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    unordered_map<string, int> groups;
    groups.reserve(n + q);
    vector<Rec> rules, queries;
    vector<int> ans(q);
    size_t nl = 0, nr = 0;
    auto read = [&](bool rule, int index) {
        string a, b;
        cin >> a >> b;
        if (a.size() != b.size())
            return;
        int l = 0, len = a.size();
        while (l < len && a[l] == b[l])
            l++;
        if (l == len)
            return;
        int r = len - 1;
        while (a[r] == b[r])
            r--;
        string key = a.substr(l, r - l + 1) + "#" + b.substr(l, r - l + 1);
        auto it = groups.find(key);
        int g;
        if (it == groups.end()) {
            g = groups.size();
            groups.emplace(move(key), g);
        } else
            g = it->second;
        Rec rec = {a.substr(0, l), a.substr(r + 1), g, index, 0, 0};
        nl += rec.left.size();
        nr += rec.right.size();
        (rule ? rules : queries).push_back(move(rec));
    };
    for (int i = 0; i < n; i++)
        read(true, i);
    for (int i = 0; i < q; i++)
        read(false, i);
    Trie left(nl), right(nr);
    for (auto *vec : {&rules, &queries})
        for (auto &r : *vec) {
            r.L = left.insert(r.left, true);
            r.R = right.insert(r.right, false);
        }
    left.build();
    right.build();
    vector<Ev> events;
    events.reserve(rules.size() * 2 + queries.size());
    for (auto &r : rules) {
        auto a = left.nodes[r.L], b = right.nodes[r.R];
        events.push_back({r.group, a.tin, 0, b.tin, b.tout, 1, 0});
        events.push_back({r.group, a.tout + 1, 0, b.tin, b.tout, -1, 0});
    }
    for (auto &r : queries)
        events.push_back({r.group, left.nodes[r.L].tin, 1, right.nodes[r.R].tin, 0, 0, r.index});
    sort(events.begin(), events.end());
    vector<int> bit(right.nodes.size() + 2);
    auto add = [&](int p, int v) {
        for (; p < (int)bit.size(); p += p & -p)
            bit[p] += v;
    };
    for (auto e : events) {
        if (e.type == 0) {
            add(e.y, e.delta);
            add(e.z + 1, -e.delta);
        } else {
            int sum = 0;
            for (int x = e.y; x; x -= x & -x)
                sum += bit[x];
            ans[e.id] = sum;
        }
    }
    for (int x : ans)
        cout << x << "\n";
}