#673. CPREFIX

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Beginner Free Contest 15

Cho xâu S độ dài N ≤ 10^5 . Tính và đưa ra dãy t_1, t_2, ..., t_N với t_i là số lần xuất hiện của xâu S[1...i] trong xâu S .

Dữ liệu vào:

  • Gồm một dòng duy nhất chứa xâu S chỉ gồm các chữ cái Latin thường độ dài không vượt quá 10^5 .

Dữ liệu ra:

  • Một dòng duy nhất in ra các giá trị t_1, t_2, ..., t_N các nhau bởi một dấu cách trống.

Ví dụ:

Dữ liệu vào:
abababa
Dữ liệu ra:
4 3 3 2 2 1 1