P16827 [AFOI 2025] D. Homophone Replacement

Time flies. That afternoon about “homophone replacement” is still clearly imprinted in little $\omega$'s mind. Back then, he insisted on exact matching: only completely identical substrings could be replaced. However, reality often did not go as hoped, and even tiny differences were enough to ruin all efforts. Many years later, when little $\omega$ opened his linguistics notes again, he gained a new understanding of “homophones”: why demand complete equality? Having the same beginning or the same ending is already “homophonic” enough. Just like bits of memory, it does not need to be fully replayed; only a beginning or an ending is enough to connect the whole story.

Little $\omega$ is an algorithm contest participant who likes linguistics. In linguistics, homophone replacement means replacing original words with words that have the same or similar pronunciation. Little $\omega$ found that the process of homophone replacement can be described using prefix or suffix relationships of strings. Specifically, little $\omega$ defines homophone replacement as the following string problem: - String $X$ is a homophone replacement of $Y$ if and only if $X$ is a **prefix** of $Y$, or $X$ is a **suffix** of $Y$. - Let the language set be $S = \{S_1, S_2, \dots, S_n\}$. A homophone triple of string $T$ means splitting $T$ into three non-empty consecutive parts $T = A + B + C$ (where $+$ denotes string concatenation), such that each part $A, B, C$ is a homophone replacement of some string in $S$. Each splitting corresponds to one string triple $(A,B,C)$, and we call this triple a homophone triple of string $T$. Two homophone triples $(A_1, B_1, C_1)$ and $(A_2, B_2, C_2)$ are essentially different if and only if $A_1 \neq A_2$ or $B_1 \neq B_2$ or $C_1 \neq C_2$. Now you are given $n$ strings $S_1, S_2, \dots, S_n$ as the language set, and $m$ strings $T_1, T_2, \dots, T_m$ as the language materials to be analyzed. For each $T_i$, please help little $\omega$ find how many essentially different homophone triple schemes there are.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$). The next $n$ lines each contain a string $S_i$, representing a word in the language set. The next $m$ lines each contain a string $T_i$, representing the material to be analyzed.

Output $m$ lines. The $j$-th line ($1 \le j \le m$) contains a non-negative integer, indicating how many essentially different homophone triples $T_j$ has.

### Sample 1 Explanation The $12$ essentially different homophone triples are as follows: - $(\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})$ ### Constraints Let $|X|$ be the length of string $X$, $L_1 = \sum\limits_{i = 1}^{n} |S_i|$, and $L_2 = \sum\limits_{i = 1}^{m} |T_i|$. For all testdata, it is guaranteed that: - $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$; - For all $1 \le i \le n$, each $S_i$ contains only uppercase and lowercase English letters. - For all $1 \le i \le m$, each $T_i$ contains only uppercase and lowercase English letters. | Test Point ID | $n , m \le$ | $L_1$ | $L_2 \le$ | Special Property | |--|--|--|--|--| | $1, 2$ | $100$ | $200$ | $200$ | None | | $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$ | None | | $13, 14$ | ^ | $5 \times 10^5$ | $3 \times 10^5$ | A | | $15, 16$ | ^ | ^ | ^ | B | | $17 \sim 20$ | ^ | ^ | ^ | None | Special property A: $m = 1$. Special property B: For all $1 \le i \le n$, each $S_i$ ends with `z`. For all $1 \le i \le m$, each $T_i$ does not contain `z`. Translated by ChatGPT 5