Najkrótszy okres [B]
Limit pamięci: 128 MB
Okresem słowa nazywamy takie słowo , które jest nie dłuższe niż i dla którego istnieje liczba naturalna ,
taka że jest prefiksem (tj. początkowym fragmentem) słowa .
Okresami słowa taktakt są więc tak, taktak oraz taktakt.
Nauczycielka napisała na tablicy bardzo długie słowo.
Jaś niezainteresowany lekcją wypisał w zeszycie wszystkie słowa powstałe przez usunięcie ze słowa na tablicy jednej literki.
Teraz chciałby wybrać takie słowo z zeszytu, którego najkrótszy okres ma jak najmniejszą długość.
Napisz program, który rozwiąże jego problem.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę przypadków testowych.
Dalej następuje wierszy.
Każdy z nich zawiera jedną liczbę całkowitą ()
oznaczającą długość słowa napisanego na tablicy, po czym następuje
słowo składające się z małych liter alfabetu angielskiego.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
-ty wiersz powinien zawierać odpowiedź na -te zapytanie:
jedną liczbę całkowitą równą długości najkrótszego ze wszystkich najkrótszych okresów
słów wypisanych w zeszycie Jasia.
Przykład
Dla danych wejściowych:
1
8 ababcaba
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu:
Dla słowa z powyższego przykładu Jaś zapisze w zeszycie słowa, których najkrótsze okresy mają następujące długości:
- babcaba - 5,
- aabcaba - 6,
- abbcaba - 6,
- abacaba - 4,
- abababa - 2,
- ababcba - 6,
- ababcaa - 6,
- ababcab - 5.
Zatem przez usunięcie literki
c z piątej pozycji otrzymujemy słowo, którego najkrótszy okres ma długość 2.
Nie jest możliwe usunięcie innej litery tak, by otrzymać słowo o jeszcze krótszym najkrótszym okresie.
Autor zadania: Jacek Tomasiewicz.