[CSP-S 2025] 谐音替换（replace）（特殊性质 B 测试）
P1015 [CSP-S 2025] 谐音替换（replace）（特殊性质 B 测试）
题目描述
小 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, 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\) 个问题。
输出格式
输出 \(q\) 行，其中第 \(j\) (\(1 \leq j \leq q\)) 行包含一个非负整数，表示替换后得到字符串 \(t_{j,2}\) 的字符串 \(t_{j,1}\) 的替换的数量。
输入输出样例 #1
输入 #1
4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb
输出 #1
2
0
输入输出样例 #2
输入 #2
3 4
a b
b c
c d
aa bb
aa b
a c
b a
输出 #2
0
0
0
0
说明/提示
【样例 1 解释】
对于小 W 的第一个询问，共有 \(2\) 种 \(t_{1,1}\) 的替换能够得到 \(t_{1,2}\):
- 令 \(x, z\) 均为空串，\(y = \text{xabcx}\), \(i = 1\)，则 \(y' = \texttt{xadex}\)，替换后得到 \(\text{xadex}\)；
- 令 \(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}\)。
| 测试点编号 | \(n, q \leq\) | \(L_1, L_2 \leq\) | 特殊性质 |
|---|---|---|---|
| \(1, 2\) | \(10^2\) | \(200\) | 无 |
| \(3 \sim 5\) | \(10^3\) | \(2\,000\) | 无 |
| \(6\) | \(10^3\) | \(10^6\) | AB |
| \(7, 8\) | \(10^4\) | \(10^6\) | A |
| \(9, 10\) | \(2 \times 10^5\) | \(10^6\) | B |
| \(11, 12\) | \(2 \times 10^5\) | \(2 \times 10^6\) | 无 |
| \(13, 14\) | \(2 \times 10^5\) | \(5 \times 10^6\) | A |
| \(15, 16\) | \(2 \times 10^5\) | \(5 \times 10^6\) | B |
| \(17 \sim 20\) | \(2 \times 10^5\) | \(5 \times 10^6\) | 无 |
特殊性质 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}\) 均为特别的。
