Đếm biên (border) của mỗi tiền tố

Cho xâu $S$ độ dài $N$ chỉ gồm chữ cái thường.

Một biên (border) của xâu $T$ độ dài $k$ là một số nguyên $L$ với $1\le L<k$ sao cho $T[1\dots L]=T[k-L+1\dots k]$ (tiền tố độ dài $L$ trùng với hậu tố độ dài $L$, hai phần này có thể chồng lấp). Biên là thực sự vì $L<k$.

Với mỗi $k$ từ $1$ tới $N$, hãy đếm số biên của tiền tố $S[1\dots k]$.

Dữ liệu vào

• Dòng duy nhất: xâu $S$.

Dữ liệu ra

Một dòng gồm $N$ số nguyên cách nhau bởi dấu cách: số biên của tiền tố $S[1\dots k]$ với $k=1,2,\dots ,N$.

Ràng buộc

• $1\le N\le {10}^6$
• $S$ chỉ gồm chữ cái Latin thường (a–z).

Ví dụ

Ghi chú

• Nếu $N=1$ thì in ra duy nhất số $0$.