[CSP-S 2025] 谐音替换_信奥算法普及+/提高

题目描述

小 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

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

输出#1

2
0

输入#2

3 4
a b
b c
c d
aa bb
aa b
a c
b a

输出#2

输入#3


见选手目录下的 `replace/replace3.in` 与 `replace/replace3.ans`。该样例满足测试点 11,12 的约束条件。

输出#3


见选手目录下的 `replace/replace3.in` 与 `replace/replace3.ans`。该样例满足测试点 11,12 的约束条件。

输入#4


见选手目录下的 `replace/replace4.in` 与 `replace/replace4.ans`。该样例满足测试点 15,16 的约束条件。

输出#4


见选手目录下的 `replace/replace4.in` 与 `replace/replace4.ans`。该样例满足测试点 15,16 的约束条件。

说明/提示

样例 1 解释

对于小 W 的第一个询问，共有 2 种 $t_{1,1}$ 的替换能够得到 $t_{1,2}$ :

令 $x, z$ 均为空串， $y = \text{xabcx}$ , $i = 1$ ，则 $y' = \text{xadex}$ ，替换后得到 $\text{xadex}$ ;
令 $x = \text{xa}$ , $y = \text{bc}$ , $z = \text{x}$ , $i = 3$ ，则 $y' = \text{de}$ ，替换后得到 $\text{xadex}$ 。

数据范围

设 $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 ~ 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 ~ 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}$ 均为特别的。