P5357 [Template] Aho–Corasick Automaton.

This problem was originally called “Aho–Corasick Automaton (Second Enhanced Version)”. Before solving this problem, you may first solve [Aho–Corasick Automaton (Easy Version)](https://www.luogu.com.cn/problem/P3808) and [Aho–Corasick Automaton (Easy Version II)](https://www.luogu.com.cn/problem/P3796), which cover simpler applications of the Aho–Corasick automaton.

You are given a text string $S$ and $n$ pattern strings $T_{1 \sim n}$. Please find, for each pattern string $T_i$, the number of times it appears in $S$.

The first line contains a positive integer $n$, representing the number of pattern strings. The next $n$ lines each contain a non-empty string $T_i$ consisting of lowercase English letters, where the $i$-th line corresponds to $T_i$. The last line contains a non-empty string $S$ consisting of lowercase English letters. **The testdata does not guarantee that any two pattern strings are different**.

Output $n$ lines. The $i$-th line contains a non-negative integer, representing the number of times $T_i$ appears in $S$.

For $100\%$ of the data, $1 \le n \le 2 \times {10}^5$, the total length of $T_{1 \sim n}$ is at most $2 \times {10}^5$, and the length of $S$ is at most $2 \times {10}^6$. Translated by ChatGPT 5