A6511 | [CSP-S 2025] 谐音替换

样例 1 解释

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

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

2. 令 $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}$。

特殊性质 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}$ 均为特别的。