Byteasar works in Byteland Centre for Computational Biology.
He has just received a long sequence of
genomes.
His task is to find frequently occurring cyclic fragments
of this sequence.
Byteasar's sequence can be represented as a word
of capital English letters.
A cyclic fragment of
is a word
such that all its cyclic rotations1 are subwords of
.
Byteasar is interested in cyclic fragments of a given length
.
For a given cyclic fragment
of
, we define the number of cyclic occurrences of
in
as the total number of occurrences of distinct cyclic rotations of
within
.
Byteasar wants to find a cyclic fragment of length
of the word
that
has the largest number of cyclic occurrences.
Please, write a program to help him.
The first line of the input contains two integers
and
(
,
) which denote
the length of the sequence of genomes and the number of queries to answer.
The second line contains a word
composed of
capital letters of the English alphabet.
The following
lines contain numbers
(
) defining the length of the cyclic fragments to consider.
Your program should output
lines.
The
-th line should contain one integer denoting the maximal number of
cyclic occurrences of any
-letter cyclic fragment of
.
For the input data:
16 2 AABAABACDABAABAA 6 3
the correct result is:
4 10
Explanation of the example: 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.
Task author: Jakub Radoszewski.
1. 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
is a subword of
, if
is a subsequence of
consisting of several consecutive letters of
.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.