#10059. [CSP-S 2025] 谐音替换（暂无数据）

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 个字符串二元组，第 () 个字符串二元组为 ，满足 ，其中 表示字符串 的长度。

对于字符串 ，定义 的替换如下：

• 对于 的某个子串 ，若存在 满足 ，则将 替换为 。具体地，设 ，其中 和 可以为空，“+” 表示字符串拼接，则 的替换将得到字符串 。

小 W 提出了 个问题，第 () 个问题会给定两个不同的字符串 ，她想知道有多少种字符串 的替换能够得到字符串 。两种 的替换不同当且仅当子串 的位置不同或用于替换的二元组 不同，即 不同或 不同。你需要回答小 W 提出的所有问题。

输入的第一行包含两个正整数 ，分别表示字符串二元组的数量和小 W 提出的问题的数量。

输入的第 () 行包含两个字符串 ，表示第 个字符串二元组。

输入的第 () 行包含两个字符串 ，表示小 W 提出的第 个问题。

输出 行，其中第 () 行包含一个非负整数，表示替换后得到字符串 的字符串 的替换的数量。

输入 #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

0
0
0
0

【样例 1 解释】

对于小 W 的第一个询问，共有 种 的替换能够得到 :

1. 令 均为空串，, ，则 ，替换后得到 ；
2. 令 , , , ，则 ，替换后得到 。

【样例 3】

见选手目录下的 与 。

该样例满足测试点 11, 12 的约束条件。

【样例 4】

见选手目录下的 与 。

该样例满足测试点 15, 16 的约束条件。

【数据范围】

设 , 。对于所有测试数据，保证:

• ;
• ;
• 对于所有 , 均仅包含小写英文字母，且 ;
• 对于所有 , 均仅包含小写英文字母，且 。

::cute-table{tuack}

特殊性质 A：。

特殊性质 B：定义字符串 为特别的，当且仅当字符串 仅包含字符 和 ，且字符 在 中出现恰好一次。对于所有 , 均为特别的，且对于所有 , 均为特别的。