Một viền của xâu S là một xâu không rỗng vừa là tiền tố vừa là hậu tố của S. Chỉ xét các viền ngắn hơn toàn bộ S. Hãy liệt kê độ dài của tất cả các viền theo thứ tự tăng dần.
Input
Một dòng chứa xâu S.
Output
Nếu có viền, in các độ dài của chúng theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có viền nào, in 0.
Constraints
1≤∣S∣≤106.
S chỉ gồm các chữ cái thường tiếng Anh.
Scoring
Subtask 1 (50% số điểm): ∣S∣≤200.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
aaaaa
Output
1 2 3 4
Giải thích: Với mỗi độ dài từ một đến bốn, tiền tố toàn ký tự a trùng với hậu tố cùng độ dài. Độ dài năm không được tính vì viền phải ngắn hơn toàn xâu.
Lời giải tóm tắt
Phân tích: Liệt kê mọi độ dài d với 1 ≤ d < |S| sao cho tiền tố dài d của S bằng hậu tố dài d của S. Prefix-function lưu độ dài tiền tố dài nhất còn có thể tái sử dụng sau mỗi ký tự, nên toàn bộ dữ liệu được xử lý mà không quay lại các vị trí đã loại.
Thuật toán: Tính prefix-function rồi bắt đầu từ pi[n-1], lần theo pi[x-1] để lấy mọi border và đảo danh sách.
Chứng minh: Trong khi quét, trạng thái KMP luôn bằng độ dài tiền tố dài nhất của mẫu hoặc của chính xâu đang xét trùng với hậu tố đã đọc. Mỗi lần lùi chỉ đi qua một border hợp lệ, nên không bỏ sót khả năng nối tiếp; quy tắc ghi nhận và chuyển trạng thái của bài vì thế tạo đúng toàn bộ kết quả cần in. Các kết quả được xử lý theo thứ tự vị trí hoặc độ dài tăng dần như contract yêu cầu, nên không đếm trùng và không đảo thứ tự.
Độ phức tạp: Thuật toán chạy tuyến tính theo tổng kích thước input và dùng bộ nhớ tuyến tính theo xâu được xây prefix-function, ngoài phần output bắt buộc.