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:1s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR ERL FANTOM FORTH GOSU GRV JS-RHINO JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Pochodzenie:Własne

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.