Problem
Es wurde eine nicht leere S -Zeichenfolge angegeben, deren Länge N \(10^6\). Nehmen wir an, dass die Elemente der Zeile von 1 bis N nummeriert sind.
Für jede i -Position eines Zeichens in einer Zeichenfolge werden wir an einer Teilzeichenfolge interessiert sein, die an dieser Position endet und mit einem bestimmten Anfang der gesamten Zeichenfolge übereinstimmt. Im Allgemeinen wird es mehrere solcher Teilstrings geben, mindestens zwei. Die längste davon hat die Länge i, sie wird uns nicht interessieren. Und die längste dieser Teilzeichenfolgen wird uns interessieren (beachten Sie, dass eine solche Teilzeichenfolge immer existiert; Wenn Sie nichts anderes finden, wird eine leere Teilzeichenfolge als letztes Mittel verwendet).
Durch den Wert der Präfix-Funktion \(\pi[i]\) werden wir die Länge dieser Teilzeichenfolge berücksichtigen.
Die Präfix-Funktion wird in verschiedenen Stringverarbeitungsalgorithmen verwendet. Insbesondere können Sie damit schnell das Problem lösen, das Vorkommen einer Zeile in eine andere zu finden («ein Muster im Text suchen»).
Ist für alle i von 1 bis N erforderlich, um \(\pi[i]\) zu berechnen.
Eingabe
Eine Zeile der Länge N, \(0 < N <= 10^6\), bestehend aus kleinen lateinischen Buchstaben.
Ausgabe
Geben Sie
N Zahlen aus, — die Präfixfunktionswerte für jede Position, getrennt durch ein Leerzeichen.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
abracadabra |
0 0 0 1 0 1 0 1 2 3 4 |