Đăng nhập

canuc80k4802·3/50

Viền Của Chuỗi

Nộp bài trên LQDOJ

Bài 48 · Z Function

Một border của là một xâu vừa là tiền tố vừa là hậu tố của , nhưng phải ngắn hơn . Hãy liệt kê độ dài của mọi border.

Input

  • Một dòng chứa xâu .

Output

  • In các độ dài border theo thứ tự tăng dần. Nếu không có border, in .

Constraints

  • .
  • chỉ gồm chữ cái thường .

Scoring

  • Subtask (): .
  • Subtask (): Không có giới hạn bổ sung.

Example

Test 1

Input

abcababcab

Output

2 5

Giải thích: Tiền tố ab và abcab lần lượt cũng là hai hậu tố của xâu; không có độ dài nào khác thỏa mãn.

Lời giải tóm tắt
  • Ý tưởng: Tính Z; độ dài L là border khi Z[n-L] đạt ít nhất L.
  • Chứng minh đúng: Hậu tố độ dài L bắt đầu ở n-L. Theo định nghĩa, Z[n-L] là số ký tự đầu hậu tố trùng tiền tố; nó đạt L đúng khi toàn bộ hai đoạn bằng nhau. Duyệt L=1..n-1 vừa loại toàn xâu vừa cho thứ tự tăng.
  • Độ phức tạp: O(n) thời gian và O(n) bộ nhớ.
  • Mẫu công khai: So sánh các tiền tố và hậu tố của abcababcab cho thấy chỉ độ dài 2 và 5 trùng nhau.