19334번 - Consistent Occurrences 출처다국어

Let us define a consistent set of occurrences of string $t$ in string $s$ as a set of occurrences of $t$ in $s$ such that no two occurrences intersect (in other words, no character position in $s$ belongs to two different occurrences).

You are given a string $s$ consisting of $n$ lowercase English letters, and $m$ queries. Each query contains a single string $t_i$.

For each query, print the maximum size of a consistent set of occurrences of $t$ in $s$.

The first line contains two space-separated integers $n$ and $m$: the length of string $s$ and the number of queries ($1 \le n \le 10^{5}$, $1 \le m \le 10^{5}$).

The second line contains the string $s$ consisting of $n$ lowercase English letters.

Each of the next $m$ lines contains a single string $t_i$ consisting of lowercase English letters: the $i$-th query ($1 \le |t_i| \le n$, where $|t_i|$ is the length of the string $t_i$).

It is guaranteed that the total length of all $t_i$ does not exceed $10^{5}$ characters.

For each query $i$, print one integer on a separate line: the maximum size of a consistent set of occurrences of $t_i$ in $s$.