Polish version    English version  
  Historia OI -> XIII OI 2005/2006 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: Okresy słów

Dostępna pamięc: 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 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 istnieje taki napis B, że A = PB. Inaczej mówiąc, prefiksy A to początkowe fragmenty A. Jeśli dodatkowo P $ \neq$% WIDTH=16 HEIGHT=30 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 są 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$ \le$% WIDTH=16 HEIGHT=30 k$ \le$% WIDTH=16 HEIGHT=30 1 000 000) -- długość napisu W kolejnym wierszu znajduje się ciąg dokładnie k 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





Wersja do druku