Hồ sơ hàm tiền tố

Bối cảnh và bài toán

Một bộ phân tích chuỗi cần lưu "hồ sơ tự khớp" tại từng vị trí. Với mỗi tiền tố kết thúc tại vị trí i, hệ thống muốn biết độ dài lớn nhất của một tiền tố của toàn chuỗi cũng đồng thời là hậu tố của đoạn s[0..i].

Yêu cầu

Tính mảng hàm tiền tố pi của chuỗi và in pi[0], pi[1], ..., pi[n-1].

Input

Một dòng chứa chuỗi s.

Output

In n số nguyên là các giá trị của hàm tiền tố.

Ràng buộc

• 1 <= |s| <= 10^6
• s chỉ gồm chữ cái thường a..z.

Chấm điểm

Ví dụ 1

Input

abaabca

Output

0 0 1 1 2 0 1

Giải thích. Ví dụ pi[4]=2 vì đoạn abaab có tiền tố/hậu tố chung dài nhất là ab.

Ví dụ 2

Input

aaaa

Output

0 1 2 3

Giải thích. Mỗi vị trí kéo dài border trước đó thêm một ký tự.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: CSES Problem Set – String Functions – String Functions (2107).