Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Dựng mảng hậu tố

    Cho xâu SSS độ dài nnn (chỉ số 0..n−10..n-10..n−1). Mảng hậu tố (suffix array) là hoán vị sa[0],…,sa[n−1]sa[0], \dots, sa[n-1]sa[0],…,sa[n−1] của các chỉ số sao cho các hậu tố S[sa[0]..],S[sa[1]..],…S[sa[0]..], S[sa[1]..], \dotsS[sa[0]..],S[sa[1]..],… được sắp xếp tăng dần theo thứ tự từ điển.

    Hãy dựng và in mảng hậu tố. Sử dụng phương pháp sắp xếp tiền tố nhân đôi (prefix doubling) đạt O(nlog⁡2n)O(n\log^2 n)O(nlog2n) hoặc tốt hơn.

    Ví dụ: S=S = S= banana. Các hậu tố sắp xếp cho mảng hậu tố 5 3 1 0 4 2.

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

      Một dòng chứa xâu SSS gồm các chữ cái la-tinh thường.

    • Ràng buộc đầu vào:

      1≤∣S∣≤2⋅1051 \le |S| \le 2\cdot10^51≤∣S∣≤2⋅105.

    • Định dạng đầu ra:

      In nnn số là mảng hậu tố (chỉ số bắt đầu từ 000), cách nhau bởi dấu cách.

    Ví dụ:

    Đầu vào:

    banana

    Đầu ra:

    5 3 1 0 4 2

    Giải thích:

    Các hậu tố theo thứ tự từ điển: a (vị trí 5), ana (3), anana (1), banana (0), na (4), nana (2). Do đó mảng hậu tố là 5 3 1 0 4 2.

    Đang tải editor...