小 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 的替换如下：
小 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} 的替换的数量。
4 2 xabcx xadex ab cd bc de aa bb xabcx xadex aaaa bbbb
2 0
3 4 a b b c c d aa bb aa b a c b a
0 0 0 0
对于小 W 的第一个询问，共有 2 种 t_{1,1} 的替换能够得到 t_{1,2}:
见选手目录下的 replace/replace3.in 与 replace/replace3.ans。
该样例满足测试点 11, 12 的约束条件。
见选手目录下的 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}|。对于所有测试数据，保证:
| 测试点编号 | n, q \leq | L_1, L_2 \leq | 特殊性质 |
|---|---|---|---|
| 1, 2 | 10^2 | 200 | 无 |
| 3 \sim 5 | 10^3 | 2\,000 | |
| 6 | 10^6 | AB | |
| 7, 8 | 10^4 | A | |
| 9, 10 | 2 \times 10^5 | B | |
| 11, 12 | 2 \times 10^6 | 无 | |
| 13, 14 | 5 \times 10^6 | A | |
| 15, 16 | B | ||
| 17 \sim 20 | 无 |
特殊性质 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} 均为特别的。
replace.zip (1.02 MB)
CSP-J/S 2025 第二轮认证