W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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.
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 .
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.