Problem

2 /2


PICADILLO

Theory Click to read/hide

El hash de una cadena es una representación de una cadena como un número único (asumiremos que la posibilidad de una colisión es insignificante) para cada cadena. Esto le permite almacenar datos importantes (como contraseñas) en la base de datos no como cadenas, sino como números. Esto le permite proteger las contraseñas si un atacante obtiene acceso a la base de datos de contraseñas, ya que no obtendrá las contraseñas en sí, sino solo su representación numérica, y es casi imposible obtener una cadena por su hash (especialmente sin conocer el algoritmo hash). ). 
Los valores hash de polinomios se utilizan con mayor frecuencia en la programación de problemas de competencia.
Una de las mejores formas de determinar la función hash de la cadena S es la siguiente:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Problem

El programador Vasya tuvo mala suerte: en lugar de unas vacaciones, lo enviaron a un viaje de negocios a una conferencia científica. "Necesitamos aumentar el nivel de conocimiento", dijo el jefe, "Se está llevando a cabo una importante conferencia sobre criptografía en Francia, y allí encriptaron en la época de Richelieu y descifraron los cifrados de otras personas en la época de Vieta".
Vasya descubrió rápidamente que ya había visto todas las pinturas del Louvre en alguna parte, la vista de la Torre Eiffel se volvió aburrida para él incluso antes de que el ratón la limpiara de la alfombra, y hacemos pirámides de vidrio para todo tipo de quioscos y restaurantes dudosos. En una palabra, simplemente no había nada que ver en París, no había dónde pescar, por lo que Vasya tuvo que asistir a los informes de la conferencia.
Uno de los oradores, una vez más tratando de desentrañar los cifrados de Bacon, presentó la hipótesis de que la clave de los misterios de Bacon se puede encontrar analizando todas las subcadenas posibles de las obras de Bacon. "¡Pero hay demasiados de ellos!" Vasya se sorprendió en voz alta. "¡No, no tanto!" - gritó el orador - "¡Calcula y lo verás por ti mismo!"
La misma noche, Vasya encontró las obras completas de Bacon en Internet. Escribió un programa que convertía los textos en una línea larga, eliminando todos los espacios y signos de puntuación de los textos. Y ahora Vasya está muy desconcertada: ¿cómo contar el número de subcadenas diferentes de esta cadena? 

Entrada
La entrada contiene una cadena no vacía recibida por Vasya. La cadena consta únicamente de caracteres latinos en minúsculas. Su extensión no supera los 2000 caracteres. 

Salida
Imprime el número de subcadenas diferentes de esta cadena.

 

Ejemplos

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1 aaba 8