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.