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.