Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KNUTH_PI - Funkcja prefiksowa Knutha

Napisz program, który dla danego tekstu (wzorca) P[1..n] wypisze tzw. funkcję prefiksową Knutha, która jest zdefiniowana nastepująco dla j=1,2,...,n

f(j) = długość najdłuższego prefisku słowa P[1..(j-1)], który jest sufiksem słowa P[2..j], czyli również słowa P[1..j].

Wejście

W pierszym wierszu dana jest liczba naturalna T - oznaczająca liczbę danych testowych. W następnych T wierszach znajduje się jedno słowo P[1..n] o długości nie przekraczającej 1000000, złożone tylko z liter a-z i A-Z.

Wyjście

Dla każdego zestawu danych, tj. dla każdego słowa P[1..n] wypisz w osobnym wierszu jego funkcję prefiksową Knutha w postaci ciągu n liczb f(1), f(2), ..., f(n) oddzielonych pojedynczym odstępem

Przykład

Wejście:
3
abab
abcabcxyab
aaabababaaaba


Wyjście:
0 0 1 2 
0 0 0 1 2 3 0 0 1 2 
0 1 2 0 1 0 1 0 1 2 3 4 5 

Dodane przez:Rafal Nowak
Data dodania:2007-04-24
Limit czasu wykonania programu:0.152s-0.310s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO
Pochodzenie:Własne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.