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.