P16827 [AFOI 2025] D.谐音替换

时光荏苒，那个关于“谐音替换”的下午，依旧清晰地印在小 $\omega$ 的脑海里。 那时的他，执着于精确的匹配：必须完全相同的子串，才能进行替换。然而，现实往往不尽如人意，细微的差别就足以让一切努力付诸东流。 多年以后，当小 $\omega$ 再次翻开语言学笔记，他对“谐音”有了新的理解：何必苛求完全一致？只需拥有相同的前后，便已足够谐音。就像回忆中的点滴，不必完整重现，只需一个开头或一个结尾，便能串联起整个故事。

小 $\omega$ 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 $\omega$ 发现，谐音替换的过程可以用字符串的前缀或后缀关系来进行描述。具体地，小 $\omega$ 将谐音替换定义为以下字符串问题： - 字符串 $X$ 是 $Y$ 的谐音替换，当且仅当 $X$ 是 $Y$ 的**前缀**，或 $X$ 是 $Y$ 的**后缀**。 - 记语言集合为 $S = \{S_1, S_2, \dots, S_n\}$。字符串 $T$ 的一个谐音三元组是指将 $T$ 分成三个非空的连续段 $T = A + B + C$（其中 $+$ 表示字符串拼接），使得每一段 $A, B, C$ 均是 $S$ 中的某个字符串的谐音替换，每一种划分方案对应一个字符串三元组 $(A,B,C)$，我们称这个三元组为字符串 $T$ 的一个谐音三元组。 两个谐音三元组 $(A_1, B_1, C_1)$ 和 $(A_2, B_2, C_2)$ 本质不同，当且仅当 $A_1 \neq A_2$ 或 $B_1 \neq B_2$ 或 $C_1 \neq C_2$。 现在给出 $n$ 个字符串 $S_1, S_2, \dots, S_n$ 作为语言集合，再给出 $m$ 个字符串 $T_1, T_2, \dots, T_m$ 作为待分析的语言资料。 请对于每个 $T_i$，帮助小 $\omega$ 求出有多少种本质不同的谐音三元组方案。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$）。 接下来 $n$ 行，每行一个字符串 $S_i$，表示语言集合中的单词。 接下来 $m$ 行，每行一个字符串 $T_i$，表示待分析的资料。

输出 $m$ 行，其中第 $j$（$1 \le j \le m$）行包含一个非负整数，表示 $T_j$ 有多少种本质不同的谐音三元组。

### 【样例1解释】 $12$ 种本质不同的谐音三元组如下： - $(\text{a},\text{bbcabb},\text{cabb})$ - $(\text{ab},\text{bcabb},\text{cabb})$ - $(\text{abb},\text{cabb},\text{cabb})$ - $(\text{abbc},\text{a},\text{bbcabb})$ - $(\text{abbc},\text{ab},\text{bcabb})$ - $(\text{abbc},\text{abb},\text{cabb})$ - $(\text{abbc},\text{abbc},\text{abb})$ - $(\text{abbc},\text{abbca},\text{bb})$ - $(\text{abbc},\text{abbcab},\text{b})$ - $(\text{abbca},\text{b},\text{bcabb})$ - $(\text{abbca},\text{bb},\text{cabb})$ - $(\text{abbcab},\text{b},\text{cabb})$ ### 【数据范围】 设 $|X|$ 为字符串 $X$ 的长度，$L_1 = \sum\limits_{i = 1}^{n} |S_i|$，$L_2 = \sum\limits_{i = 1}^{m} |T_i|$。对于所有测试数据，保证： - $1 \le n , m \le 10^5$； - $1 \le |S_i|$，$3 \le |T_i|$； - $1 \le L_1 \le 5 \times 10^5$，$3 \le L_2 \le 3 \times 10^5$； - 对于所有 $1 \le i \le n$，$S_i$ 均仅包含大小写英文字母。 - 对于所有 $1 \le i \le m$，$T_i$ 均仅包含大小写英文字母。 | 测试点编号 | $n , m \le$ | $L_1$ | $L_2 \le$ | 特殊性质 | |--|--|--|--|--| | $1, 2$ | $100$ | $200$ | $200$ | 无 | | $3 \sim 5$ | $10^3$ | $2\,000$ | $2\,000$ | ^ | | $6$ | ^ | $10^5$ | $10^5$ | A、B | | $7, 8$ | $10^4$ | ^ | ^ | A | | $9, 10$ | $10^5$ | ^ | ^ | B | | $11, 12$ | ^ | $2 \times 10^5$ | $2 \times 10^5$ | 无 | | $13, 14$ | ^ | $5 \times 10^5$ | $3 \times 10^5$ | A | | $15, 16$ | ^ | ^ | ^ | B | | $17 \sim 20$ | ^ | ^ | ^ | 无 | 特殊性质 A：$m = 1$。 特殊性质 B：对于所有 $1 \le i \le n$，$S_i$ 均以 `z` 结尾。对于所有 $1 \le i \le m$，$T_i$ 均不包含 `z`。