Biologia obliczeniowa
Limit pamięci: 128 MB
Bajtazar pracuje w Bajtockim Centrum Biologii Obliczeniowej.
Właśnie dostał do analizy długą sekwencję złożoną z genomów.
Jego zadaniem jest znalezienie często powtarzających się cyklicznych fragmentów
tej sekwencji.
Sekwencję Bajtazara można reprezentować jako słowo złożone z wielkich
liter alfabetu angielskiego.
Cyklicznym fragmentem słowa nazywamy takie słowo , że wszystkie
obroty cykliczne1 słowa są podsłowami słowa .
Bajtazara interesują cykliczne fragmenty słowa o ustalonej długości .
Dla danego cyklicznego fragmentu słowa , definiujemy
liczbę cyklicznych wystąpień w jako łączną liczbę wystąpień
wszystkich różnych obrotów cyklicznych słowa w słowie .
Bajtazar chciałby znaleźć w słowie cykliczny fragment długości , dla którego
liczba cyklicznych wystąpień jest jak największa.
Napisz program, który pomoże mu w tym zadaniu.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
oraz (, ),
oznaczające długość sekwencji genomów oraz liczbę przypadków testowych do rozważenia.
W drugim wierszu znajduje się -literowe słowo złożone z liter
'A''Z' stanowiące reprezentację sekwencji.
Dalej następuje wierszy, z których -ty zawiera jedną liczbę całkowitą
(), oznaczającą rozważaną długość cyklicznych fragmentów sekwencji.
Wyjście
Twój program powinien wypisać wierszy.
Każdy z tych wierszy powinien zawierać jedną liczbę całkowitą, oznaczającą
maksymalną liczbę cyklicznych wystąpień -literowego cyklicznego fragmentu słowa .
Przykład
Dla danych wejściowych:
16 2
AABAABACDABAABAA
6
3
poprawną odpowiedzią jest:
4
10
Wyjaśnienie do przykładu:
Cykliczny fragment AABAAB występuje w podanym słowie 4 razy:
raz jako AABAAB, dwa razy jako ABAABA i raz jako
BAABAA.
Cykliczny fragment AAB występuje w tym słowie 10 razy.
Autor zadania: Jakub Radoszewski.
1. Obrotem cyklicznym słowa nazywamy słowo powstałe przez
(potencjalnie wielokrotne) przeniesienie ostatniej litery słowa na początek.
Przykładowo, wszystkimi obrotami cyklicznymi słowa ABAABA są:
ABAABA, BAABAA oraz AABAAB.
Słowo nazywamy podsłowem słowa , jeśli występuje w jako
spójny kawałek.