Deixa-me ouvir a tua voz, conta-me as histórias da tua viagem —
Tanto as alegrias como as dores, e também aqueles encontros que ficaram gravados no coração.
Descrição
É dada uma cadeia de caracteres $S$ de comprimento $n$, com índices a partir de $1$. Denotamos por $S(i, j)=S_iS_{i+1}\cdots S_j$ a subcadeia de $S$ formada pelos caracteres do índice $i$ ao índice $j$.
Se uma cadeia não vazia $B$ for simultaneamente um prefixo e um sufixo de uma cadeia $X$, e $|B|<|X|$, dizemos que $B$ é uma borda de $X$, onde $|X|$ representa o comprimento da cadeia $X$.
Inicialmente, estás na subcadeia $S(1, n)$. Cada salto é realizado da seguinte forma:
- Escolhe uma subcadeia $X$ da subcadeia em que te encontras atualmente.
- Escolhe uma borda $B$ de $X$, com a condição de que $2|B|\ge |X|$.
- Salta para a subcadeia correspondente a $B$ enquanto prefixo ou sufixo de $X$, escolhendo qualquer uma das duas.
Por exemplo, quando $S$ é aabaaba e estás em $S(1, 7)$, podes escolher $X=S(2, 7)=$ abaaba. A sua borda aba tem comprimento exatamente igual a metade de $|X|$, pelo que podes saltar para $S(2, 4)$ ou $S(5, 7)$.
Para cada $1\le i\le n$, determina separadamente o número máximo de saltos que podes realizar, partindo de $S(1, n)$ e terminando em $S(i, i)$. Se não for possível lá chegar, a resposta é $-1$. É permitido não realizar nenhum salto.
Há vários casos de teste.
Entrada
A primeira linha contém um inteiro $T$, que indica o número de casos de teste.
Seguem-se os casos de teste, por ordem. Para cada caso de teste, é dada uma linha que representa a cadeia $S$.
Saída
Para cada caso de teste, imprime uma linha com $n$ inteiros, em que o $i$-ésimo inteiro representa a resposta para $S(i, i)$ (se não for possível chegar a $S(i, i)$, imprime -1).
Exemplos
Entrada 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Saída 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
No primeiro caso de teste, $S=$ abbababbab, e tanto o seu prefixo como o seu sufixo de comprimento $5$ são abbab. É possível realizar os seguintes dois saltos:
- Primeiro, salta para $S(1, 5)$; depois, escolhe $S(2, 3)=$ bb e salta para $S(2, 2)$ ou $S(3, 3)$.
- Primeiro, salta para $S(6, 10)$; depois, escolhe $S(7, 8)=$ bb e salta para $S(7, 7)$ ou $S(8, 8)$.
Só é possível continuar a saltar se o primeiro salto for para uma das duas subcadeias abbab acima. O salto seguinte só pode chegar a um único carácter, pelo que o número máximo de saltos para cada uma destas quatro posições é $2$.
Não é possível chegar às restantes posições através de saltos, pelo que a resposta é $-1$.
Exemplo 2
Consulta wind2.in e wind2.ans nos anexos. Este exemplo satisfaz as restrições da subtarefa 3.
Exemplo 3
Consulta wind3.in e wind3.ans nos anexos. Este exemplo satisfaz as restrições da subtarefa 5.
Exemplo 4
Consulta wind4.in e wind4.ans nos anexos. Este exemplo satisfaz as restrições da subtarefa 6.
Exemplo 5
Consulta wind5.in e wind5.ans nos anexos. Este exemplo satisfaz as restrições da subtarefa 8.
Restrições
Neste problema, estão ativadas dependências razoáveis entre subtarefas.
| Subtarefa | $n\le$ | $\sum n\le$ | Propriedade especial | Pontos |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Nenhuma | $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$ | Nenhuma | $12$ |
Propriedade especial A: existe uma cadeia não vazia $P$ tal que $S$ é um prefixo da cadeia periódica infinita $P^{\infty}$ e $|P|\le 10$.
Propriedade especial B: $S$ é gerada aleatoriamente, isto é, cada carácter de $S$ é escolhido de forma uniformemente aleatória de um conjunto de caracteres de tamanho $\ge 2$.
Propriedade especial C: para todo $1\le i<n$, verifica-se $S_i\neq S_{i+1}$.
Para todos os dados, é garantido que $1\le n\le 2\times 10^5$ e que a soma dos comprimentos das cadeias de todos os casos de teste num mesmo ficheiro de teste satisfaz $\sum n\le 2\times 10^5$. A cadeia $S$ contém apenas letras minúsculas do alfabeto inglês.