Prefiksufiks

Limit pamięci: 64 MB

W tym zadaniu będą nas interesować napisy złożone z małych liter alfabetu angielskiego. Prefiksem danego napisu nazwiemy dowolny jego początkowy fragment. Sufiksem danego napisu nazwiemy dowolny jego końcowy fragment. W szczególności, pusty napis jest zarówno prefiksem jak i sufiksem dowolnego napisu. Dwa napisy nazywamy cyklicznie równoważnymi, jeżeli jeden z nich można uzyskać z drugiego, przestawiając pewien jego sufiks z końca napisu na początek. Dla przykładu, napisy i są równoważne cyklicznie, a napisy i nie są. W szczególności, każdy napis jest sam sobie cyklicznie równoważny.

Dany jest napis złożony z liter. Szukamy jego prefiksu i sufiksu , obu tej samej długości, takich że:

• i są sobie równoważne cyklicznie,
• długość i nie przekracza (czyli prefiks i sufiks nie zachodzą na siebie w ), oraz
• długość i jest jak największa.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą długość danego napisu . Drugi wiersz wejścia zawiera napis składający się z małych liter alfabetu angielskiego.

W testach wartych 30% punktów zachodzi dodatkowy warunek .

W testach wartych 50% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą, równą długości szukanego prefiksu i sufiksu .

Przykład

Dla danych wejściowych:

15
ababbabababbaab

poprawną odpowiedzią jest:

6

Autor zadania: Jacek Tomasiewicz.