385. 【25CSPS提高组】谐音替换 中等

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题： 给定 $n$ 个字符串二元组，第 $i (1 ≤ i ≤ n)$ 个字符串二元组为 ($s_{i,1}, s_{i,2}$)，满足$|s_{i,1}| = |s_{i,2}|$，其中 $|s|$ 表示字符串 $s$ 的长度。 对于字符串 $s$，定义 $s$ 的替换如下： • 对于 $s$ 的某个子串 $y$，若存在 $1 ≤ i ≤ 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 ≤ j ≤ m)$ 个问题会给定两个不同的字符串 $t_{j,1}, t_{j,2}$，她想知道有多少种字符串 $t_{j,1}$ 的替换能够得到字符串 $t_{j,2}$。两种 $s$ 的替换不同当且仅当子串$y$ 的位置不同或用于替换的二元组($s_{i,1}, s_{i,2}$) 不同，即 $x, z$ 不同或 $i$ 不同。你需要回答小 W 提出的所有问题。