Dấu Vết Tiền Tố · canuc80k4800

Với xâu $S$ có độ dài $n$ , đặt $Z_{0} = n$ . Với mỗi $i > 0, Z_{i}$ là số lớn nhất $L (0 \leq L \leq n - i)$ sao cho $S_{0}, \dots, S_{L - 1} = S_{i}, \dots, S_{i + L - 1}$ . Hãy tính toàn bộ mảng này; các vị trí được đánh số từ $0$ .

Input

Một dòng chứa xâu $S$ gồm các chữ cái thường tiếng Anh.

Output

In $n$ số nguyên $Z_{0}, Z_{1}, \dots, Z_{n - 1}$ trên một dòng.

Constraints

$1 \leq n \leq 5 \cdot 1 0^{5}$ .
Mọi ký tự của $S$ nằm trong $a, \dots, z$ .

Scoring

Subtask $1$ ( $50%$ ): $n \leq 2000$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

abacaba

Output

7 0 1 0 3 0 1

Giải thích: Ở vị trí $4$ ( $0$ -based), hậu tố aba trùng ba ký tự đầu của xâu nên $Z_{4} = 3$ ; các giá trị khác được xác định tương tự.

Ý tưởng: Duy trì hộp Z phải nhất [l,r], tái sử dụng giá trị trong hộp rồi mở rộng ngoài biên.
Chứng minh đúng: Trong hộp [l,r], đoạn S[l..r] trùng tiền tố. Vì vậy tại i≤r ta biết chắc ít nhất min(r-i+1,Z[i-l]) ký tự khớp. Vòng so sánh tiếp chỉ kiểm tra phần chưa được chứng minh; khi dừng, giá trị thu được là LCP tối đại. Mỗi lần mở rộng ngoài hộp làm r tăng nên tổng số phép mở rộng là tuyến tính.
Độ phức tạp: O(n) thời gian và O(n) bộ nhớ.
Mẫu công khai: So sánh từng hậu tố với tiền tố cho xâu abacaba cho dãy 7,0,1,0,3,0,1.