Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Un string es una secuencia finita de letras minúsculas del alfabeto inglés. Particularmente puede ser una secuencia vacía, es decir, de longitud $0$. Por $A = BC$ denotamos que el string $A$ es obtenido como concatenación de los strings $B$ y $C$. Un string $P$ se dice prefijo de $A$ si existe $B$ tal que $A = PB$, si $B$ no es un string vacío se dice que $P$ es un prefijo propio de $A$. Un string $P$ es un periodo de $A$ si $A$ es prefijo (no necesariamente propio) de $PP$, y $P$ es prefijo propio de $A$. Por ejemplo, $\texttt{abab}$ y $\texttt{ababab}$ son ambos periodos de $\texttt{abababa}$. El periodo máximo de un string $A$ es el periodo de longitud máxima de $A$, o el string vacío, si $A$ no tiene ningún periodo. En este ejercicio usted tiene que calcular la suma de las longitudes de los periodos máximos de cada prefijo de un string dado.

En la primera línea de la entrada un entero $n$ $(1 \leq n \leq 1000000)$ - la longitud del string. En la segunda línea una secuencia de $n$ letras minúsculas del alfabeto inglés.