시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 2 | 2 | 2 | 100.000% |
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$.
6 4 aaaaaa a aa aaa aaaa
6 3 2 1