Problem
Data una stringa non vuota S la cui lunghezza N non supera \(10^6\). Supponiamo che gli elementi della stringa siano numerati da 1 a N.
Per ogni posizione del carattere i nella stringa, saremo interessati alla sottostringa che termina in quella posizione e corrisponde a qualche inizio dell'intera stringa. In generale, ci saranno diverse sottostringhe di questo tipo, almeno due. Il più lungo di essi ha la lunghezza i, non ci interesserà. E saremo interessati alla più lunga delle rimanenti sottostringhe di questo tipo (nota che una tale sottostringa esiste sempre — nel caso estremo, se non viene trovato nient'altro, andrà bene una sottostringa vuota).
Il valore della funzione prefisso \(\pi[i]\) sarà la lunghezza di questa sottostringa.
La funzione prefisso viene utilizzata in vari algoritmi di elaborazione delle stringhe. In particolare, può essere utilizzato per risolvere rapidamente il problema di trovare l'occorrenza di una stringa in un'altra ("ricerca di uno schema nel testo").
Obbligatorio per tutti gli i da 1 a N per calcolare \(\pi[i ] \).
Input
Una stringa di lunghezza N, \(0 < N <= 10^6\), composta da lettere latine minuscole .
Uscita
Emetti
N numeri — prefisso valori di funzione per ogni posizione, separati da spazi.
Esempi
| # |
Input |
Uscita |
| 1 |
abracadabra |
0 0 0 1 0 1 0 1 2 3 4 |