5564: P14363 [CSP-S 2025] 谐音替换 / replace（官方数据）
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：
给定 $n$ 个字符串二元组，第 $i$ ($1 \leq i \leq n$) 个字符串二元组为 $(s_{i,1}, s_{i,2})$，满足 $|s_{i,1}| = |s_{i,2}|$，其中 $|s|$ 表示字符串 $s$ 的长度。
对于字符串 $s$，定义 $s$ 的替换如下：
- 对于 $s$ 的某个子串 $y$，若存在 $1 \leq i \leq n$ 满足 $y = s_{i,1}$，则将 $y$ 替换为 $y' = s_{i,2}$。具体地，设 $s = x + y + z$，其中 $x$ 和 $z$ 可以为空，“+” 表示字符串拼接，则 $s$ 的替换将得到字符串 $s' = x + y' + z$。
小 W 提出了 $q$ 个问题，第 $j$ ($1 \leq j \leq q$) 个问题会给定两个不同的字符串 $t_{j,1}, t_{j,2}$，她想知道有多少种字符串 $t_{j,1}$ 的替换能够得到字符串 $t_{j,2}$。两种 $s$ 的替换不同当且仅当**子串 $y$ 的位置不同或用于替换的二元组 $(s_{i,1}, s_{i,2})$ 不同**，即 $x, z$ 不同或 $i$ 不同。你需要回答小 W 提出的所有问题。
给定 $n$ 个字符串二元组，第 $i$ ($1 \leq i \leq n$) 个字符串二元组为 $(s_{i,1}, s_{i,2})$，满足 $|s_{i,1}| = |s_{i,2}|$，其中 $|s|$ 表示字符串 $s$ 的长度。
对于字符串 $s$，定义 $s$ 的替换如下：
- 对于 $s$ 的某个子串 $y$，若存在 $1 \leq i \leq n$ 满足 $y = s_{i,1}$，则将 $y$ 替换为 $y' = s_{i,2}$。具体地，设 $s = x + y + z$，其中 $x$ 和 $z$ 可以为空，“+” 表示字符串拼接，则 $s$ 的替换将得到字符串 $s' = x + y' + z$。
小 W 提出了 $q$ 个问题，第 $j$ ($1 \leq j \leq q$) 个问题会给定两个不同的字符串 $t_{j,1}, t_{j,2}$，她想知道有多少种字符串 $t_{j,1}$ 的替换能够得到字符串 $t_{j,2}$。两种 $s$ 的替换不同当且仅当**子串 $y$ 的位置不同或用于替换的二元组 $(s_{i,1}, s_{i,2})$ 不同**，即 $x, z$ 不同或 $i$ 不同。你需要回答小 W 提出的所有问题。
Input
输入的第一行包含两个正整数 $n, q$，分别表示字符串二元组的数量和小 W 提出的问题的数量。
输入的第 $i+1$ ($1 \leq i \leq n$) 行包含两个字符串 $s_{i,1}, s_{i,2}$，表示第 $i$ 个字符串二元组。
输入的第 $j+n+1$ ($1 \leq j \leq q$) 行包含两个字符串 $t_{j,1}, t_{j,2}$，表示小 W 提出的第 $j$ 个问题。
输入的第 $i+1$ ($1 \leq i \leq n$) 行包含两个字符串 $s_{i,1}, s_{i,2}$，表示第 $i$ 个字符串二元组。
输入的第 $j+n+1$ ($1 \leq j \leq q$) 行包含两个字符串 $t_{j,1}, t_{j,2}$，表示小 W 提出的第 $j$ 个问题。
Output
输出 $q$ 行，其中第 $j$ ($1 \leq j \leq q$) 行包含一个非负整数，表示替换后得到字符串 $t_{j,2}$ 的字符串 $t_{j,1}$ 的替换的数量。
Sample Input Copy
4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbbSample Output Copy
2
0HINT
【样例 1 解释】
对于小 W 的第一个询问，共有 $2$ 种 $t_{1,1}$ 的替换能够得到 $t_{1,2}$:
1. 令 $x, z$ 均为空串，$y = \text{xabcx}$, $i = 1$，则 $y' = \texttt{xadex}$，替换后得到 $\text{xadex}$；
2. 令 $x = \texttt{xa}$, $y = \texttt{bc}$, $z = \texttt{x}$, $i = 3$，则 $y' = \texttt{de}$，替换后得到 $\texttt{xadex}$。
【样例 3】
见选手目录下的 $replace/replace3.in$ 与 $replace/replace3.ans$。
该样例满足测试点 11, 12 的约束条件。
【样例 4】
见选手目录下的 $replace/replace4.in$ 与 $replace/replace4.ans$。
该样例满足测试点 15, 16 的约束条件。
【数据范围】
设 $L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|$, $L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|$。对于所有测试数据，保证:
- $1 \leq n, q \leq 2 \times 10^5$;
- $2 \leq L_1, L_2 \leq 5 \times 10^6$;
- 对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均仅包含小写英文字母，且 $|s_{i,1}| = |s_{i,2}|$;
- 对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均仅包含小写英文字母，且 $t_{j,1} \neq t_{j,2}$。
特殊性质 A：$q = 1$。
特殊性质 B：定义字符串 $s$ 为**特别的**，当且仅当字符串 $s$ 仅包含字符 $a$ 和 $b$，且字符 $b$ 在 $s$ 中出现**恰好**一次。对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均为特别的，且对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均为特别的。
对于小 W 的第一个询问，共有 $2$ 种 $t_{1,1}$ 的替换能够得到 $t_{1,2}$:
1. 令 $x, z$ 均为空串，$y = \text{xabcx}$, $i = 1$，则 $y' = \texttt{xadex}$，替换后得到 $\text{xadex}$；
2. 令 $x = \texttt{xa}$, $y = \texttt{bc}$, $z = \texttt{x}$, $i = 3$，则 $y' = \texttt{de}$，替换后得到 $\texttt{xadex}$。
【样例 3】
见选手目录下的 $replace/replace3.in$ 与 $replace/replace3.ans$。
该样例满足测试点 11, 12 的约束条件。
【样例 4】
见选手目录下的 $replace/replace4.in$ 与 $replace/replace4.ans$。
该样例满足测试点 15, 16 的约束条件。
【数据范围】
设 $L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|$, $L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|$。对于所有测试数据，保证:
- $1 \leq n, q \leq 2 \times 10^5$;
- $2 \leq L_1, L_2 \leq 5 \times 10^6$;
- 对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均仅包含小写英文字母，且 $|s_{i,1}| = |s_{i,2}|$;
- 对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均仅包含小写英文字母，且 $t_{j,1} \neq t_{j,2}$。
特殊性质 B：定义字符串 $s$ 为**特别的**，当且仅当字符串 $s$ 仅包含字符 $a$ 和 $b$，且字符 $b$ 在 $s$ 中出现**恰好**一次。对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均为特别的，且对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均为特别的。