Giới thiệu cơ bản

Mảng hậu tố (Suffix Array) là một cấu trúc dữ liệu mạnh mẽ trong xử lý chuỗi, cho phép giải quyết hiệu quả nhiều bài toán liên quan đến chuỗi con. Cho một chuỗi S có độ dài n, ta định nghĩa các khái niệm cơ bản sau:

• S_i: Hậu tố bắt đầu tại vị trí i của chuỗi S (tức là chuỗi S[i...n]).
• sa[i]: Lưu trữ chỉ số bắt đầu của hậu tố đứng thứ i khi tất cả các hậu tố được sắp xếp theo thứ tự từ điển.
• rk[i]: Thứ hạng (rank) của hậu tố S_i trong mảng đã sắp xếp. Ta có quan hệ rk[sa[i]] = i.
• h[i]: Độ dài tiền tố chung lớn nhất (LCP - Longest Common Prefix) giữa hậu tố thứ i và hậu tố thứ i-1 trong mảng sa. Công thức: h[i] = lcp(S_sa[i], S_sa[i-1]).

Thuật toán xây dựng Suffix Array

Cách tiếp cận vét cạn có độ phức tạp O(n²log n) là không khả thi cho dữ liệu lớn. Thay vào đó, ta sử dụng kỹ thuật "nhân đôi" (doubling) kết hợp với sắp xếp cơ số (radix sort) để đạt được độ phức tạp O(n log n).

Ý tưởng chính là trong bước thứ k, ta sắp xếp các hậu tố dựa trên 2^k ký tự đầu tiên. Để làm điều này, ta coi mỗi hậu tố là một cặp gồm hai khóa: khóa thứ nhất là thứ hạng của 2^k-1 ký tự đầu, và khóa thứ hai là thứ hạng của 2^k-1 ký tự tiếp theo. Việc sắp xếp cặp này được thực hiện bằng Radix sort (sắp xếp theo khóa thứ hai trước, sau đó đến khóa thứ nhất với thuật toán ổn định).

const int MAX_SIZE = 1000005;

struct SuffixArray {
    int char_data[MAX_SIZE];
    int freq[MAX_SIZE];      // Mảng đếm tần suất cho radix sort
    int old_rank[MAX_SIZE];  // Lưu thứ hạng cũ để so sánh
    int rank_arr[MAX_SIZE];  // Mảng thứ hạng hiện tại
    int suffix_arr[MAX_SIZE];// Mảng kết quả SA
    int temp_idx[MAX_SIZE];  // Mảng chỉ số tạm thời
    int n, max_val;

    void build(int len, int char_range) {
        n = len;
        max_val = max(n, char_range);
        
        // Khởi tạo: mỗi ký tự là một khóa
        for (int i = 1; i <= n; i++) freq[rank_arr[i] = char_data[i]]++;
        for (int i = 1; i <= max_val; i++) freq[i] += freq[i-1];
        for (int i = n; i >= 1; i--) suffix_arr[freq[rank_arr[i]]--] = i;

        // Bắt đầu nhân đôi độ dài
        for (int step = 1; step < n; step <<= 1) {
            memset(freq, 0, sizeof(freq));
            int cnt = 0;

            // Sắp xếp theo khóa thứ hai (rk[i + step])
            // Những phần không có khóa thứ hai (n - step + 1 .. n) có thứ tự nhỏ nhất
            for (int i = n - step + 1; i <= n; i++) temp_idx[++cnt] = i;
            for (int i = 1; i <= n; i++) if (suffix_arr[i] > step) temp_idx[++cnt] = suffix_arr[i] - step;

            // Sắp xếp theo khóa thứ nhất (rk[i]) dựa trên thứ tự của temp_idx
            for (int i = 1; i <= n; i++) freq[rank_arr[i]]++;
            for (int i = 1; i <= max_val; i++) freq[i] += freq[i-1];
            for (int i = n; i >= 1; i--) suffix_arr[freq[rank_arr[temp_idx[i]]]--] = temp_idx[i];

            // Cập nhật thứ hạng mới
            cnt = 0;
            memcpy(old_rank, rank_arr, sizeof(rank_arr));
            for (int i = 1; i <= n; i++) {
                bool is_same = (old_rank[suffix_arr[i]] == old_rank[suffix_arr[i-1]]) && 
                               (old_rank[suffix_arr[i] + step] == old_rank[suffix_arr[i-1] + step]);
                rank_arr[suffix_arr[i]] = is_same ? cnt : ++cnt;
            }
            if (cnt == n) break; // Đã sắp xếp xong toàn bộ
        }
    }
};

Tính toán mảng chiều cao (Height Array)

Để tính mảng h[i], ta sử dụng tính chất quan trọng: h[rk[i]] ≥ h[rk[i-1]] - 1. Điều này có nghĩa là độ dài LCP của hậu tố hiện tại với hậu tố đứng trước nó ít nhất giảm đi 1 so với cặp trước đó.

Dựa trên tính chất này, ta có thể tính mảng h trong thời gian tuyến tính O(n) bằng cách duyệt qua chỉ số ban đầu của chuỗi và sử dụng kết quả của bước trước để khởi tạo giá trị đếm.

void compute_height(int n, int *s, int *sa, int *rk, int *h) {
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (rk[i] == 1) { 
            h[rk[i]] = 0; 
            continue; 
        }
        if (k) k--; // Giảm độ dài so với bước trước
        int j = sa[rk[i] - 1]; // Hậu tố đứng trước trong SA
        // Mở rộng độ dài chung
        while (s[i + k] == s[j + k]) k++;
        h[rk[i]] = k;
    }
}

Các ứng dụng thực tế

1. Kiểm tra chuỗi con và đếm số lần xuất hiện
Vì mọi chuỗi con đều là tiền tố của một hậu tố nào đó, và các hậu缀 đã được sắp xếp, ta có thể tìm kiếm chuỗi con P bằng cách nhị phân trên mảng sa. Nếu tìm thấy, một khoảng liên tục trong sa sẽ đại diện cho tất cả các vị trí xuất hiện của P.

2. Tìm LCP của hai hậu缀 bất kỳ
Bài toán tìm lcp(S_i, S_j) có thể quy về tìm giá trị nhỏ nhất trên đoạn của mảng h. Cụ thể, giả sử rk[i] < rk[j], thì lcp(S_i, S_j) = min(h[rk[i]+1], ..., h[rk[j]]). Vấn đề này có thể giải quyết bằng Sparse Table (RMQ) với độ phức tạp O(1) sau khi tiền xử lý.

3. Đếm số lượng chuỗi con khác nhau
Tổng số chuỗi con là n(n+1)/2. Tuy nhiên, các chuỗi con trùng l nhau được tính nhiều lần. Mỗi hậu缀 S_sa[i] sẽ đóng góp len(S_sa[i]) - h[i] chuỗi con mới (tổng độ dài trừ đi phần trùng với hậu tố đứng trước). Kết quả là \sum (n - sa[i] + 1 - h[i]).

4. Bài toán chuỗi con xuất hiện ít nhất K lần (VD: P2852)
Một chuỗi con xuất hiện ít nhất K lần khi là tiền tố chung của K hậu tố liên tiếp. Ta chỉ cần duyệt một cửa sổ trượt kích thước K trên mảng h và tìm giá trị min lớn nhất trong các cửa sổ đó.

5. Đếm dạng chuỗi AABB (VD: P1117)
Ta có thể liệt kê độ dài len của chuỗi A. Với mỗi độ dài này, các vị trí kết thúc của các khối A tiềm năng cách nhau len. Bài toán trở thành tìm LCP và LCS (Longest Common Suffix) giữa các cặp vị trí thỏa mãn khoảng cách, sau đó sử dụng mảng hiệu (prefix sum) để tính tổng số cách hợp lệ.

6. Xây dựng chuỗi tối ưu (VD: P2870)
Bài toán lấy ký tự từ đầu hoặc cuối chuỗi để tạo chuỗi kết quả có thứ tự từ điển nhỏ nhất. Khi hai đầu bằng nhau, ta cần so sánh chuỗi con từ trái sang phải và chuỗi con từ phải sang trái. Cách giải quyết là nối chuỗi gốc S và chuỗi đảo S', chèn một ký tự đặc biệt giữa chúng, rồi xây dựng Suffix Array cho chuỗi tổng hợp này để so sánh trực tiếp.

7. Tính tổng khoảng cách giữa các cặp hậu tố (VD: P4248)
Công thức cần tính có thể quy về việc tính tổng LCP của tất cả các cặp hậu缀. Vấn đề này tương đương với việc tính tổng các giá trị nhỏ nhất trên tất cả các đoạn con của mảng h. Kỹ thuật stack đơn điệu (monotonic stack) thường được sử dụng để giải quyết bài toán này trong thời gian tuyến tính.

8. Tối ưu hóa chuỗi tránh các mẫu (VD: ABC268Ex)
Để đảm bảo các chuỗi S_i không xuất hiện trong T, ta cần thay đổi ít nhất một ký tự trong mỗi lần xuất hiện của chúng. Sử dụng Suffix Array để xác định các khoảng (intersects) chứa các chuỗi bị cấm. Bài toán trở thành việc chọn số điểm tối thiểu trên trục số để cắt hết các khoảng này (giải thuật tham lam).