English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Biologia obliczeniowa (bio)
Computational Biology
Memory limit: 128 MB
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.
Input
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.
Output
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 
.
Example
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 
.