Background

This problem was originally called “Aho–Corasick Automaton (Second Enhanced Version)”. Before solving this problem, you may first solve Aho–Corasick Automaton (Easy Version) and Aho–Corasick Automaton (Easy Version II), which cover simpler applications of the Aho–Corasick automaton.

Problem Description

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$.

Input Format

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 Format

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

5
a
bb
aa
abaa
abaaa
abaaabaa

6
0
3
2
1

Hint

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