Program I Wielki Problem

[MitS]

Witam!

Mam pewien problem, a mianowicie mam zadanie:

 

Treść:
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 A = BC, oznacza, że A jest napisem powstałym przez sklejenie napisów B i C (w tej kolejności). Napis P jest prefiksem napisu A, jeżeli istnije taki napis B, że A = PB. Inaczej mówiąc, prefiksy A to początkowe fragmenty A. Jeśli dodatkowo P jest różne od  A oraz P nie jest napisem pustym, to mówimy, że P jest prefiksem właściwym A.
Napis Q jest okresem A, jeśli Q jest prefiksem właściwym A oraz A jest prefiksem (niekoniecznie właściwym) napisu QQ. Przykładowo, napisy abab i ababab soą okresami napisu abababa. Maksymalnym okresem napisu A nazywamy najdłuższy z jego okresów, lub napis pusty, jeśli A 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 k (1 <= k <= 1 000 000) - długość napisu. W kolejnym wierszu znajduje się ciag dokładnie k małych liter alfabetu angielskiego - napis.

Wyjście:
W pierwszym i jednym wierszu standardowego wyjścia Twój program powinien zapisać jedna liczbę - sumę długości maksymalnych okresów wszystkich prefiksów napisu zadanego na wejściu.

Przykład:
Dla danych wejściowych:
8
babababa
poprawnym wynikiem jest:
24

 

I tak... to jest moje zadanie, z którym mam problem, bo nie wiem nawet jak się do niego zabrać, gdyby istniała jakaś dobra dusza na forum która pomogła by mi zrobić te zadanie byłbym wdzięczny.

 

Język C++

I tak nie proszę od razu o cały kod lub gotowe zasdanie (choć tym bym nie pogardził) lecz na jakiś zbiór punktów co po kolei mam wykonać, jakieś wzory i wytłumaczenie co to jest ten prefiks ???

 

Pozdrawiam i naprawde będe dozgonnie wdzieczny