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.