Hướng giải của Xây dựng Suffix Array

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Suffix Array bằng Doubling + Sort

Phân tích

Xây dựng mảng hậu tố bằng thuật toán "doubling" (gấp đôi). Ở mỗi bước, ta so sánh các hậu tố theo cặp (rank[i], rank[i + k]) với k tăng dần theo lũy thừa 2. Khi k >= n, các hậu tố được sắp xếp hoàn toàn.

Độ phức tạp

  • Thời gian: O(N log N · log N) với comparator, hoặc O(N log N) với Radix Sort
  • Không gian: O(N)

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    vector<int> sa(n), rank(n), tmp(n);
    // Khoi tao: rank[i] = ma ASCII cua ky tu s[i]
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];  // Dung ma ASCII de so sanh
    }

    // Vong lap doubling: k = 1, 2, 4, 8, ...
    for (int k = 1; k < n; k *= 2) {
        // So sanh hau to theo cap (rank[i], rank[i+k])
        auto cmp = [&](int a, int b) {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = (a + k < n) ? rank[a + k] : -1;
            int rb = (b + k < n) ? rank[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);

        // Cap nhat rank moi
        tmp[sa[0]] = 0;  // Hau to nho nhat co rank = 0
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
        }
        rank = tmp;
    }

    for (int i = 0; i < n; i++) {
        cout << sa[i] << (i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

Giải thích

  • Mỗi vòng lặp, k tăng gấp đôi, giúp so sánh được tiền tố dài hơn.
  • Sau log(n) vòng lặp, các hậu tố đứng đầu xâu khác biệt hoàn toàn và sắp xếp đúng.
  • Khi a + k >= n, ta coi rank = -1 để xâu ngắn hơn luôn xếp trước.
  • Sort với comparator O(N log N), tổng cả thuật toán O(N log² N).

Nhận xét

Không có ý kiến tại thời điểm này.