▍题意

给定 $n$ 个字符串替换规则 $(s_{i,1},s_{i,2})$，其中 $|s_{i,1}|=|s_{i,2}|$。对于 $q$ 个询问，每个询问给出两个字符串 $t_1$ 和 $t_2$，求有多少种将 $t_1$ 的某个子串 $y$（等于某个 $s_{i,1}$）替换为对应的 $s_{i,2}$ 后能得到 $t_2$ 的方法。两种方法不同当且仅当子串位置不同或使用的规则不同。

数据范围：$n,q\le 2\times 10^5$，$\sum |s_{i,1}|+|s_{i,2}|\le 5\times 10^6$，$\sum |t_{j,1}|+|t_{j,2}|\le 5\times 10^6$。

▍分析

思路：构建特殊的 AC 自动机，其中 Trie 树的边以字符对 $(c_1,c_2)$ 为标识，同时匹配 $t_1$ 和 $t_2$ 的对应字符。

1. 特殊 Trie 树构建：将每个规则 $(s_1,s_2)$ 插入 Trie 树，边标识为 $(s_1[i],s_2[i])$ 组成的整数 $(s_1[i]{-}^{\prime }{a}^{\prime })\times 26+(s_2[i]{-}^{\prime }{a}^{\prime })$。

2. AC 自动机构建：在 Trie 树上构建 Fail 指针和 Fail 树，用于快速跳转。

3. 查询处理：对于每个查询 $(t_1,t_2)$：

   • 找到第一个不同位置 $l$ 和最后一个不同位置 $r$
   • 在 AC 自动机上匹配字符对序列 $(t_1[i],t_2[i])$
   • 对于每个位置 $i\ge r-1$，在 Fail 树上找到满足深度条件的节点，统计规则数量

4. 优化：使用倍增数组快速在 Fail 树上跳转，预处理每个节点的深度和祖先信息。

时间复杂度：$O(L_1+L_2+(n+q)\log n)$，其中 $L_1,L_2$ 分别是规则和查询的总长度。

▍参考代码

const int N = 2e5 + 5, M = 5e6 + 5, MM = 25e5;

int n, q, tot, fail[MM], dep[MM];
char s1[M], s2[M];
int tag[MM], fa[MM][22];
unordered_map<int, int> trie[MM]; // 使用哈希表存储Trie树，键为字符对编码
vector<int> g[MM];                // Fail树

// 向Trie树中添加一个替换规则
void add() {
    int now = 0; // 从根节点开始
    for (int i = 1; s1[i]; i++) {
        // 将字符对(s1[i], s2[i])编码为一个整数
        int p = (s1[i] - 'a') * 26 + s2[i] - 'a';
        // 如果当前节点没有这个字符对对应的边，创建新节点
        if (!trie[now][p]) {
            trie[now][p] = ++tot;
            dep[tot] = dep[now] + 1; // 记录节点深度
        }
        now = trie[now][p]; // 移动到下一个节点
    }
    ++tag[now]; // 标记该节点为一个规则的终点
}
// 构建AC自动机的Fail指针
void getfail() {
    queue<int> q;
    q.push(0); // 根节点的Fail指针指向自己
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        // 遍历当前节点的所有子节点
        for (auto pp : trie[x]) {
            int p = pp.first;   // 字符对编码
            int to = pp.second; // 子节点编号
            int now = fail[x];  // 从父节点的Fail指针开始

            // 在Fail链上寻找匹配的节点
            while (now && trie[now].find(p) == trie[now].end())
                now = fail[now];

            // 如果找到匹配，设置子节点的Fail指针
            if (x && trie[now].find(p) != trie[now].end())
                now = trie[now][p];
            fail[to] = now;

            // 构建Fail树
            g[now].push_back(to);
            q.push(to);
        }
    }
}
// DFS遍历Fail树，预处理倍增数组和标记前缀和
void dfs(int x) {
    for (int to : g[x]) {
        tag[to] += tag[x]; // 标记前缀和
        fa[to][0] = x;     // 直接父节点

        // 预处理倍增数组
        for (int i = 1; i <= 21; i++)
            fa[to][i] = fa[fa[to][i - 1]][i - 1];

        dfs(to);
    }
}

int read(char *s) {
    char c;
    int i = 0;
    while ((c = getchar()) < 'a' || c > 'z') continue;
    s[++i] = c;
    while ((c = getchar()) >= 'a' && c <= 'z') s[++i] = c;
    s[i + 1] = 0;
    return i;
}

int main() {
    scanf("%d%d", &n, &q);

    // 读取所有替换规则并构建Trie树
    for (int i = 1; i <= n; i++) 
        read(s1), read(s2), add();

    // 构建AC自动机
    getfail();
    dfs(0);
    // 处理每个查询
    for (int i = 1; i <= q; i++) {
        int len = read(s1), len2 = read(s2);

        // 如果长度不同，直接输出0
        if (len != len2) {
            puts("0");
            continue;
        }

        // 找到第一个和最后一个不同的字符位置
        int l = len + 1, r = 0;
        for (int i = 1; i <= len; i++)
            if (s1[i] != s2[i]) {
                l = i; // 第一个不同位置
                break;
            }
        for (int i = len; i; i--)
            if (s1[i] != s2[i]) {
                r = i; // 最后一个不同位置
                break;
            }
        int now = 0, ans = 0;
        // 在AC自动机上匹配字符对序列
        for (int i = 1; i <= len; i++) {
            int p = (s1[i] - 'a') * 26 + s2[i] - 'a';

            // 在Fail链上寻找匹配
            while (now && trie[now].find(p) == trie[now].end())
                now = fail[now];

            // 如果找到匹配，移动到对应节点
            if (trie[now].find(p) != trie[now].end())
                now = trie[now][p];

            // 当当前位置超过最后一个不同位置时，统计答案
            if (i >= r) {
                // 检查当前节点深度是否足够覆盖不同区间
                if (dep[now] < i - l + 1) continue;

                // 使用倍增找到深度刚好小于(i-l+1)的节点
                int x = now;
                for (int j = 21; j >= 0; j--)
                    if (dep[fa[x][j]] >= i - l + 1)
                        x = fa[x][j];
                x = fa[x][0]; // 移动到第一个深度不足的节点

                // 统计深度在[i-l+1, dep[now]]之间的规则数量
                ans += tag[now] - tag[x];
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}