Okresy słów
Limit pamięci: 32 MB
Napisem nazywamy każdy skończony ciąg małych liter
alfabetu angielskiego.
W szczególności może to być ciąg pusty.
Zapis oznacza, że jest napisem powstałym przez
sklejenie napisów i (w tej kolejności).
Napis jest prefiksem napisu , jeżeli istnieje
taki napis , że .
Inaczej mówiąc, prefiksy to początkowe fragmenty .
Jeśli dodatkowo oraz nie jest napisem pustym,
to mówimy, że jest prefiksem właściwym .
Napis jest okresem , jeśli jest prefiksem
właściwym oraz jest prefiksem (niekoniecznie właściwym)
napisu .
Przykładowo, napisy abab i ababab są okresami
napisu abababa.
Maksymalnym okresem napisu nazywamy najdłuższy z jego
okresów, lub napis pusty, jeśli nie posiada okresu.
Dla przykładu, maksymalnym okresem napisu ababab jest
abab.
Maksymalnym okresem abc jest napis pusty.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia długość napisu oraz napis,
-
wyznaczy sumę długości maksymalnych okresów wszystkich
jego prefiksów,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna
liczba całkowita () - długość napisu.
W kolejnym wierszu znajduje się ciąg dokładnie małych liter alfabetu
angielskiego - napis.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien
zapisać jedną liczbę - sumę długości maksymalnych okresów
wszystkich prefiksów napisu zadanego na wejściu.
Przykład
Dla danych wejściowych:
8
babababa
poprawną odpowiedzią jest:
24
Autor zadania: Szymon Acedański.