97288 - 谐音替换（replace）

时间限制 2 秒 内存限制 1024 MB

题目描述

小 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

输出

2
0

样例 2

输入

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

输出

提示

【样例 1 解释】

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

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

【数据范围】

设 $L1 = \sum{i=1}^{n} |s{i,1}| + |s{i,2}| $,$ L2 = \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}$。

来源

CSP