8287번 - Computational Biology 다국어

Byteasar works in Byteland Centre for Computational Biology. He has just received a long sequence of n genomes. His task is to find frequently occurring cyclic fragments of this sequence.

Byteasar's sequence can be represented as a word s = s₁ ... s_n of capital English letters. A cyclic fragment of s is a word t such that all its cyclic rotations¹ are subwords of s.

Byteasar is interested in cyclic fragments of a given length m. For a given cyclic fragment t of s, we define the number of cyclic occurrences of t in s as the total number of occurrences of distinct cyclic rotations of t within s. Byteasar wants to find a cyclic fragment of length m of the word s that has the largest number of cyclic occurrences. Please, write a program to help him.

¹A cyclic rotation of a word is constructed by moving its last letter to its beginning (possibly multiple times). For example, there are three different cyclic rotations of ABAABA, namely ABAABA, BAABAA and AABAAB. A word u is a subword of v, if u is a subsequence of v consisting of several consecutive letters of v.

The first line of the input contains two integers n and q (2 ≤ n ≤ 500,000, 1 ≤ q ≤ 8) which denote the length of the sequence of genomes and the number of queries to answer. The second line contains a word s composed of n capital letters of the English alphabet. The following q lines contain numbers m_i (2 ≤ m_i ≤ n) defining the length of the cyclic fragments to consider.

Your program should output q lines. The i-th line should contain one integer denoting the maximal number of cyclic occurrences of any m_i-letter cyclic fragment of s.

The cyclic fragment AABAAB occurs in the given word 4 times: once as AABAAB, twice as ABAABA and once as BAABAA. The cyclic fragment AAB occurs in this word 10 times.