A19506. 谐音替换（replace）

谐音替换（replace）

题目描述

小 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 提出的所有问题。

输入格式

从文件 replace.in 中读入数据。

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

输入的第 i+1（1 ≤ i ≤ n）行包含两个字符串 s_i,1, s_i,2，表示第 i 个字符串二元组。

输入的第 j+n+1（1 ≤ j ≤ q）行包含两个字符串 t_j,1, t_j,2，表示小 W 提出的第 j 个问题。

输出格式

输出到文件 replace.out 中。

输出 q 行，其中第 j（1 ≤ j ≤ 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

样例 1 解释

对于小 W 的第一个询问，共有 2 种 t_1,1 的替换能够得到 t_1,2：

1.令 x,z 均为空串，y = xabcx，i=1，则 y' = xadex，替换后得到 xadex；

2.令 x = xa，y = bc，z = x，i=3，则 y' = de，替换后得到 xadex。

样例 2 输入

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

样例 2 输出

0
0
0
0

样例 3

见选手目录下的 replace/replace3.in 与 replace/replace3.ans。

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

样例 4

见选手目录下的 replace/replace4.in 与 replace/replace4.ans。

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

数据范围

设 L₁ =∑ⁿ _i=1 |s_i,1| + |s_i,2|，L₂ = ∑^q _j=1 |t_j,1| + |t_j,2|。对于所有测试数据，保证：

1 ≤ n, q ≤ 2 × 10⁵；

2 ≤ L₁, L₂≤ 5 × 10⁶；

对于所有 1 ≤ i ≤ n，s_i,1, s_i,2 均仅包含小写英文字母，且 |s_i,1| = |s_i,2|；

对于所有 1 ≤ j ≤ q，t_j,1, t_j,2 均仅包含小写英文字母，且 t_j,1 ≠ t_j,2。

特殊性质A:q=1。

特殊性质B:定义字符串s为特别的，当且仅当字符串s仅包含字符a和b，且字符b在s中出现恰好一次。对于所有1 ≤ i ≤ n，s_i,1, s_i,2 均为特别的，且对于所有

1≤j≤q，t_j,1,t_j,2均为特别的。