Fais-moi entendre ta voix, raconte-moi les histoires de ton voyage —
Les moments heureux comme les moments douloureux, et ces rencontres gravées dans ton cœur.
Énoncé
On vous donne une chaîne $S$ de longueur $n$, dont les indices commencent à $1$. On note $S(i, j)=S_iS_{i+1}\cdots S_j$ la sous-chaîne de $S$ allant du caractère d’indice $i$ au caractère d’indice $j$.
Si une chaîne non vide $B$ est à la fois un préfixe et un suffixe d’une chaîne $X$, et si $|B|<|X|$, alors $B$ est appelée un bord de $X$, où $|X|$ désigne la longueur de la chaîne $X$.
Au départ, vous vous trouvez sur la sous-chaîne $S(1, n)$. Chaque saut se déroule comme suit :
- Choisissez une sous-chaîne $X$ de la sous-chaîne sur laquelle vous vous trouvez actuellement.
- Choisissez un bord $B$ de $X$ vérifiant $2|B|\ge |X|$.
- Sautez sur la sous-chaîne correspondant à l’occurrence de $B$ en tant que préfixe ou suffixe de $X$, au choix.
Par exemple, si $S$ est aabaaba et que vous vous trouvez sur $S(1, 7)$, vous pouvez choisir $X=S(2, 7)=$ abaaba. Son bord aba a une longueur exactement égale à la moitié de $|X|$ ; vous pouvez donc sauter sur $S(2, 4)$ ou $S(5, 7)$.
Pour chaque $1\le i\le n$, déterminez le nombre maximal de sauts que l’on peut effectuer en partant de $S(1, n)$ pour arriver finalement sur $S(i, i)$. Si cette sous-chaîne est inaccessible, la réponse est $-1$. Il est permis de n’effectuer aucun saut.
Il y a plusieurs cas de test.
Entrée
La première ligne contient un entier $T$, le nombre de cas de test.
Les cas de test sont ensuite donnés successivement. Chaque cas de test est constitué d’une ligne contenant la chaîne $S$.
Sortie
Pour chaque cas de test, affichez une ligne contenant $n$ entiers. Le $i$-ième entier est la réponse pour $S(i, i)$ (si $S(i, i)$ est inaccessible, affichez -1).
Exemples
Entrée 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Sortie 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
Remarque
Dans le premier cas de test, $S=$ abbababbab ; son préfixe et son suffixe de longueur $5$ sont tous deux abbab. On peut effectuer deux sauts de l’une des manières suivantes :
- Sautez d’abord sur $S(1, 5)$, puis choisissez $S(2, 3)=$ bb et sautez sur $S(2, 2)$ ou $S(3, 3)$.
- Sautez d’abord sur $S(6, 10)$, puis choisissez $S(7, 8)=$ bb et sautez sur $S(7, 7)$ ou $S(8, 8)$.
On ne peut continuer à sauter que si le premier saut mène à l’une des deux occurrences de abbab ci-dessus. Le saut suivant ne peut atteindre qu’un seul caractère ; le nombre maximal de sauts pour chacune de ces quatre positions est donc $2$.
Les autres positions ne peuvent pas être atteintes par des sauts ; leur réponse est donc $-1$.
Exemples 2
Voir wind2.in et wind2.ans dans les pièces jointes. Cet exemple respecte les contraintes de la sous-tâche 3.
Exemples 3
Voir wind3.in et wind3.ans dans les pièces jointes. Cet exemple respecte les contraintes de la sous-tâche 5.
Exemples 4
Voir wind4.in et wind4.ans dans les pièces jointes. Cet exemple respecte les contraintes de la sous-tâche 6.
Exemples 5
Voir wind5.in et wind5.ans dans les pièces jointes. Cet exemple respecte les contraintes de la sous-tâche 8.
Contraintes
Des dépendances appropriées entre les sous-tâches sont activées pour ce problème.
| Sous-tâches | $n\le$ | $\sum n\le$ | Propriété spéciale | Points |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Aucune | $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$ | Aucune | $12$ |
Propriété spéciale A : il existe une chaîne non vide $P$ telle que $S$ est un préfixe de la chaîne périodique infinie $P^{\infty}$, et $|P|\le 10$.
Propriété spéciale B : $S$ est générée aléatoirement, c’est-à-dire que chaque caractère de $S$ est choisi uniformément au hasard dans un alphabet de taille $\ge 2$.
Propriété spéciale C : pour tout $1\le i<n$, on a $S_i\neq S_{i+1}$.
Pour toutes les données, il est garanti que $1\le n\le 2\times 10^5$ et que, dans un même fichier de test, la somme des longueurs des chaînes de tous les cas de test vérifie $\sum n\le 2\times 10^5$. La chaîne $S$ ne contient que des lettres minuscules de l’alphabet anglais.