cpp-053Đọc toàn bộ đề miễn phí
Mảng hậu tố Suffix Array và mảng LCP bằng thuật toán Kasai trong O(N log N)
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy xây dựng:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: std sort, std vector, std string.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu định nghĩa Mảng hậu tố (Suffix Array - SA): Danh sách vị trí bắt đầu của các hậu tố đã được sắp xếp theo thứ tự từ điển.
- Cài đặt thuật toán nhân đôi (Prefix Doubling) xây dựng SA trong O(N log N).
- Xây dựng mảng tiền tố chung dài nhất (Longest Common Prefix - LCP) giữa hai hậu tố kề nhau trong SA bằng thuật toán Kasai trong thời gian tuyến tính O(N).
Mô tả bài toán
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy xây dựng:
- Mảng hậu tố SA (0-indexed).
- Mảng LCP kích thước N-1, trong đó LCP[i] là độ dài tiền tố chung dài nhất của hậu tố SA[i] và hậu tố SA[i+1].
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Một dòng duy nhất chứa xâu ký tự S (1 ≤ |S| ≤ 2 · 105).
Output
- Dòng 1: In N số nguyên của mảng SA, cách nhau bởi dấu cách.
- Dòng 2: In N-1 số nguyên của mảng LCP, cách nhau bởi dấu cách.
Ràng buộc
- 1 ≤ |S| ≤ 2 · 105.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
bananaOutput
5 3 1 0 4 2
1 3 0 0 2
*Giải thích:*
- Các hậu tố sắp xếp:
- 5: "a"
- 3: "ana" (LCP với "a" là 1)
- 1: "anana" (LCP với "ana" là 3)
- 0: "banana" (LCP với "anana" là 0)
- 4: "na" (LCP với "banana" là 0)
- 2: "nana" (LCP với "na" là 2)3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.