Déjame oír tu voz, cuéntame las historias de tu viaje…
Tanto las alegrías como las penas, y también esos encuentros que quedaron grabados en tu corazón.
Descripción
Se da una cadena $S$ de longitud $n$, cuyos índices comienzan en $1$. Denotamos por $S(i, j)=S_iS_{i+1}\cdots S_j$ la subcadena de $S$ formada por los caracteres desde la posición $i$ hasta la posición $j$.
Si una cadena no vacía $B$ es a la vez un prefijo y un sufijo de una cadena $X$, y $|B|<|X|$, se dice que $B$ es un borde de $X$, donde $|X|$ representa la longitud de la cadena $X$.
Inicialmente, te encuentras en la subcadena $S(1, n)$. Cada salto se realiza de la siguiente manera:
- Elige una subcadena $X$ dentro de la subcadena en la que te encuentras.
- Elige un borde $B$ de $X$ que cumpla $2|B|\ge |X|$.
- Salta a la subcadena correspondiente a $B$ como prefijo o como sufijo de $X$; puedes elegir cualquiera de las dos.
Por ejemplo, si $S$ es aabaaba y te encuentras en $S(1, 7)$, puedes elegir $X=S(2, 7)=$ abaaba. Su borde aba tiene una longitud de exactamente la mitad de $|X|$, por lo que puedes saltar a $S(2, 4)$ o a $S(5, 7)$.
Para cada $1\le i\le n$, determina por separado el número máximo de saltos que se pueden realizar partiendo de $S(1, n)$ y terminando en $S(i, i)$. Si no es posible llegar, la respuesta es $-1$. Se permite no realizar ningún salto.
Hay varios casos de prueba.
Entrada
La primera línea contiene un entero $T$, que indica el número de casos de prueba.
A continuación se proporcionan los casos de prueba, uno tras otro. Cada caso de prueba consta de una línea que contiene la cadena $S$.
Salida
Para cada caso de prueba, imprime una línea con $n$ enteros. El $i$-ésimo entero debe ser la respuesta para $S(i, i)$ (si no es posible llegar a $S(i, i)$, imprime -1).
Ejemplos
Entrada 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Salida 1
-1 2 2 -1 -1 -1 2 2 -1 -1 3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1 -1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1
Nota
En el primer caso de prueba, $S=$ abbababbab, y tanto su prefijo como su sufijo de longitud $5$ son abbab. Se pueden realizar dos saltos de las siguientes maneras:
- Primero salta a $S(1, 5)$; después, elige $S(2, 3)=$ bb y salta a $S(2, 2)$ o a $S(3, 3)$.
- Primero salta a $S(6, 10)$; después, elige $S(7, 8)=$ bb y salta a $S(7, 7)$ o a $S(8, 8)$.
Solo es posible seguir saltando si el primer salto lleva a una de las dos subcadenas abbab anteriores, y el siguiente salto solo puede llevar a un único carácter. Por tanto, el número máximo de saltos para cada una de estas cuatro posiciones es $2$.
No es posible llegar a las demás posiciones mediante saltos, por lo que su respuesta es $-1$.
Ejemplos 2
Consulta wind2.in y wind2.ans en los archivos adjuntos. Este ejemplo cumple las restricciones de la subtarea 3.
Ejemplos 3
Consulta wind3.in y wind3.ans en los archivos adjuntos. Este ejemplo cumple las restricciones de la subtarea 5.
Ejemplos 4
Consulta wind4.in y wind4.ans en los archivos adjuntos. Este ejemplo cumple las restricciones de la subtarea 6.
Ejemplos 5
Consulta wind5.in y wind5.ans en los archivos adjuntos. Este ejemplo cumple las restricciones de la subtarea 8.
Restricciones
En este problema están habilitadas las dependencias pertinentes entre subtareas.
| Subtareas | $n\le$ | $\sum n\le$ | Propiedad especial | Puntos |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Ninguna | $5$ |
| $2$ | $500$ | $14$ | ||
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $21$ | |
| $4$ | $10^5$ | $10^5$ | $18$ | |
| $5$ | $2\times 10^5$ | $2\times 10^5$ | A | $15$ |
| $6$ | B | $13$ | ||
| $7$ | C | $2$ | ||
| $8$ | Ninguna | $12$ |
Propiedad especial A: existe una cadena no vacía $P$ tal que $S$ es un prefijo de la cadena periódica infinita $P^{\infty}$ y $|P|\le 10$.
Propiedad especial B: $S$ se genera aleatoriamente; es decir, cada carácter de $S$ se elige de manera uniforme al azar de un alfabeto de tamaño $\ge 2$.
Propiedad especial C: para todo $1\le i<n$, se cumple $S_i\neq S_{i+1}$.
Para todos los datos, se garantiza que $1\le n\le 2\times 10^5$ y que la suma de las longitudes de las cadenas de todos los casos de prueba de un mismo archivo de entrada cumple $\sum n\le 2\times 10^5$. La cadena $S$ contiene únicamente letras minúsculas del alfabeto inglés.