Suffix array P63715

Un suffix array es una tabla donde se guardan, en orden alfabético, todos los sufijos de una palabra. Por ejemplo: los sufijos de la palabra MISSISSIPPI son

que una vez ordenados quedan

El suffix array de la palabra MISSISSIPPI es

donde se indica que el primer sufijo en orden alfabético es el que empieza en la posición 10 (o sea, I, teniendo en cuenta que la palabra tiene 11 letras, con posiciones de la 0 a la 10), seguido del que empieza en la posición 7 (o sea, IPPI), etc., acabando con el sufijo que empieza en la posición 2 (o sea, SSISSIPPI).

Entrada

Cada entrada contiene una única línea con una palabra formada por letras mayúsculas A-Z. Ninguna palabra tendrá menos de 2 letras.

Salida

Escribe, en una línea, el contenido del suffix array de la palabra. Separa dos elementos consecutivos con espacios, y pon un punto (.) al final de la línea. ¡No te olvides del salto de línea!

Puntuación

Hay 10 grupos de entradas. Se dará 10 puntos por resolver correctamente todas las entradas de cada grupo. Las entradas del grupo i-ésimo contendrán palabras de no más de 2, 3, 5, 10, 100, 1000, 10000, 50000, 100000, 250000 letras respectivamente. Se te garantiza que todas las palabras han sido generadas al azar (excepto el Ejemplo 1).

Observación

Existen modos muy eficientes de obtener el suffix array de una palabra, incluso para el caso de palabras que no hayan sido generadas al azar. Para resolver este problema no es necesario conocer ninguna de estas construcciones.