Lass mich deine Stimme hören und erzähle mir die Geschichten deiner Reise —
Von den freudigen und den schmerzhaften Erlebnissen und von den Begegnungen, die sich ins Herz eingeprägt haben.
Aufgabenstellung
Gegeben ist eine Zeichenkette $S$ der Länge $n$, deren Indizes bei $1$ beginnen. Mit $S(i, j)=S_iS_{i+1}\cdots S_j$ bezeichnen wir die Teilzeichenkette von $S$, die aus dem $i$-ten bis zum $j$-ten Zeichen besteht.
Ist eine nichtleere Zeichenkette $B$ sowohl Präfix als auch Suffix einer Zeichenkette $X$ und gilt $|B|<|X|$, so heißt $B$ ein Rand von $X$. Dabei bezeichnet $|X|$ die Länge der Zeichenkette $X$.
Zu Beginn befindest du dich auf der Teilzeichenkette $S(1, n)$. Jeder Sprung läuft wie folgt ab:
- Wähle innerhalb der Teilzeichenkette, auf der du dich gerade befindest, eine Teilzeichenkette $X$.
- Wähle einen Rand $B$ von $X$, für den $2|B|\ge |X|$ gilt.
- Springe auf die Teilzeichenkette, die dem Vorkommen von $B$ als Präfix oder als Suffix von $X$ entspricht. Du darfst eine der beiden wählen.
Wenn beispielsweise $S$ gleich aabaaba ist und du dich auf $S(1, 7)$ befindest, kannst du $X=S(2, 7)=$ abaaba wählen. Sein Rand aba ist genau halb so lang wie $|X|$, daher kannst du auf $S(2, 4)$ oder $S(5, 7)$ springen.
Bestimme für jedes $1\le i\le n$ einzeln die größtmögliche Anzahl von Sprüngen, mit denen du von $S(1, n)$ aus schließlich $S(i, i)$ erreichst. Ist dieses Ziel nicht erreichbar, lautet die Antwort $-1$. Es ist erlaubt, keinen einzigen Sprung auszuführen.
Es gibt mehrere Testfälle.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$, die Anzahl der Testfälle.
Anschließend folgen die Testfälle der Reihe nach. Jeder Testfall besteht aus einer Zeile mit der Zeichenkette $S$.
Ausgabe
Gib für jeden Testfall eine Zeile mit $n$ ganzen Zahlen aus. Die $i$-te Zahl ist die Antwort für $S(i, i)$ (falls $S(i, i)$ nicht erreichbar ist, gib -1 aus).
Beispiele
Eingabe 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Ausgabe 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
Hinweis
Im ersten Testfall ist $S=$ abbababbab. Sowohl sein Präfix als auch sein Suffix der Länge $5$ ist abbab. Die folgenden zwei Sprünge sind möglich:
- Springe zunächst auf $S(1, 5)$, wähle dann $S(2, 3)=$ bb und springe auf $S(2, 2)$ oder $S(3, 3)$.
- Springe zunächst auf $S(6, 10)$, wähle dann $S(7, 8)=$ bb und springe auf $S(7, 7)$ oder $S(8, 8)$.
Nur wenn du beim ersten Sprung auf eines der beiden oben genannten Vorkommen von abbab springst, kannst du danach noch einmal springen. Beim nächsten Sprung kannst du jedoch nur ein einzelnes Zeichen erreichen. Daher beträgt die maximale Anzahl von Sprüngen für jede dieser vier Positionen $2$.
Alle übrigen Positionen sind durch Sprünge nicht erreichbar, daher lautet ihre Antwort $-1$.
Beispiele 2
Siehe wind2.in und wind2.ans im Anhang. Dieses Beispiel erfüllt die Beschränkungen von Teilaufgabe 3.
Beispiele 3
Siehe wind3.in und wind3.ans im Anhang. Dieses Beispiel erfüllt die Beschränkungen von Teilaufgabe 5.
Beispiele 4
Siehe wind4.in und wind4.ans im Anhang. Dieses Beispiel erfüllt die Beschränkungen von Teilaufgabe 6.
Beispiele 5
Siehe wind5.in und wind5.ans im Anhang. Dieses Beispiel erfüllt die Beschränkungen von Teilaufgabe 8.
Beschränkungen
Für diese Aufgabe sind sinnvolle Abhängigkeiten zwischen den Teilaufgaben aktiviert.
| Teilaufgabe | $n\le$ | $\sum n\le$ | Besondere Eigenschaft | Punkte |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Keine | $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$ | Keine | $12$ |
Besondere Eigenschaft A: Es gibt eine nichtleere Zeichenkette $P$, sodass $S$ ein Präfix der unendlich wiederholten Zeichenkette $P^{\infty}$ ist und $|P|\le 10$ gilt.
Besondere Eigenschaft B: $S$ wird zufällig erzeugt, das heißt, jedes Zeichen von $S$ wird gleichverteilt zufällig aus einem Zeichensatz der Größe $\ge 2$ gewählt.
Besondere Eigenschaft C: Für alle $1\le i<n$ gilt $S_i\neq S_{i+1}$.
Für alle Daten gilt $1\le n\le 2\times 10^5$, und die Summe der Zeichenkettenlängen aller Testfälle innerhalb einer Testdatei erfüllt $\sum n\le 2\times 10^5$. Die Zeichenkette $S$ enthält ausschließlich englische Kleinbuchstaben.