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.