Bài toán: Tìm Tiền tố Cũng là Hậu tố của Chuỗi

Đề bài

Cho một số chuỗi, mỗi chuỗi có độ dài tối đa ~4 \times 10^5~. Với mỗi chuỗi, hãy tìm tất cả các độ dài của những tiền tố cũng đồng thời là hậu tố của chuỗi đó.

Định dạng đầu vào

• Một số dòng, mỗi dòng chứa một chuỗi.

Định dạng đầu ra

• Với mỗi chuỗi đầu vào, xuất ra một dòng chứa một dãy số nguyên tăng dần, biểu thị các độ dài của các tiền tố cũng đồng thời là hậu tố của chuỗi.

Ví dụ & Giải thích

Ví dụ 1

Input

ababcababababcabab
aaaaa

Output

2 4 9 18
1 2 3 4 5

Giải thích

Trường hợp 1: "ababcababababcabab"

• Các tiền tố cũng là hậu tố của chuỗi:
  • "ab" (độ dài 2)
  • "abab" (độ dài 4)
  • "ababcabab" (độ dài 9)
  • "ababcababababcabab" (độ dài 18 - chính nó)
• Do đó, output là: 2 4 9 18

Trường hợp 2: "aaaaa"

• Các tiền tố cũng là hậu tố của chuỗi:
  • "a" (độ dài 1)
  • "aa" (độ dài 2)
  • "aaa" (độ dài 3)
  • "aaaa" (độ dài 4)
  • "aaaaa" (độ dài 5 - chính nó)
• Do đó, output là: 1 2 3 4 5