P3808 AC Automaton (Simple Version)

Given $n$ pattern strings $s_i$ and a text string $t$, count how many distinct pattern strings appear in the text. Two pattern strings are different if and only if their indices are different.

The first line contains an integer $n$, the number of pattern strings. Lines $2$ to $(n + 1)$ each contain one string; the string on line $(i + 1)$ is the pattern string $s_i$ with index $i$. The last line contains a string, the text string $t$.

Output a single integer on one line, which is the answer.

### Sample 1 Explanation $s_2$ and $s_3$ have different indices, so each contributes once to the answer. ### Sample 2 Explanation $s_1$, $s_2$, and $s_4$ all appear in the string `abcd`. ### Constraints - For $10\%$ of the testdata, it is guaranteed that $n = 1$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$, $1 \leq |t| \leq 10^6$, $1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6$. $s_i, t$ contain only lowercase letters. Translated by ChatGPT 5