405021: GYM101741 K 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 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵).

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 ≤ |t_i| ≤ 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⁵ 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