Khái niệm cơ bản

Mảng hậu tố (Suffix Array) là một cấu trúc dữ liệu quan trọng trong xử lý xâu ký tự, dùng để sắp xếp tất cả các hậu tố của một xâu theo thứ tự từ điển. Cùng với mảng height, nó hỗ trợ hiệu quả cho các bài toán như tìm chuỗi con chung dài nhất, đếm số lượng xâu con phân biệt, v.v.

Ký hiệu sử dụng

• Xâu ký tự s có độ dài n, đánh chỉ số từ 1.
• s[i..j] là đoạn con từ vị trí i đến j.
• Hậu tố i: xâu s[i..n].
• sa[i]: vị trí bắt đầu của hậu tố có thứ hạng i trong thứ tự từ điển.
• rk[i]: thứ hạng của hậu tố bắt đầu tại i.

Thuật toán xây dựng mảng hậu tố – Phương pháp nhân đôi

Ý tưởng chính: So sánh các hậu tố bằng cách nhân đôi độ dài tiền tố đã biết thứ tự.

Các bước thực hiện

1. Bắt đầu bằng việc so sánh ký tự đầu tiên của mỗi hậu tố.
2. Tại mỗi bước, nếu đã biết thứ tự của các đoạn con độ dài w, ta có thể xác định thứ tự của các đoạn độ dài 2w bằng cách sắp xếp kép theo hai khóa:
   • Khóa 1: Thứ hạng của s[i..i+w-1]
   • Khóa 2: Thứ hạng của s[i+w..i+2w-1]
3. Lặp lại quá trình này cho đến khi w \ge n.

Cài đặt tối ưu với sắp xếp cơ số

Sử dụng sắp xếp cơ số để giảm độ phức tạp xuống O(n \log n).

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

const int MAXN = 1e6 + 5;

char s[MAXN];
int n, sa[MAXN], rk[MAXN], old_rk[MAXN], cnt[MAXN], tp[MAXN];

void build_suffix_array() {
    int m = 300; // Số lượng ký tự tối đa (bao gồm chữ cái và ký hiệu)
    
    // Khởi tạo: Sắp xếp theo ký tự đầu tiên
    for (int i = 1; i <= n; ++i) {
        rk[i] = s[i];
        ++cnt[rk[i]];
    }
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    // Nhân đôi độ dài
    for (int w = 1; w < n; w <<= 1) {
        // Bước 1: Tạo danh sách tạm theo khóa thứ hai
        int p = 0;
        for (int i = n - w + 1; i <= n; ++i) tp[++p] = i; // Các hậu tố ngắn hơn w
        for (int i = 1; i <= n; ++i) if (sa[i] > w) tp[++p] = sa[i] - w;

        // Bước 2: Sắp xếp cơ số theo khóa đầu tiên
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
        for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; --i) sa[cnt[rk[tp[i]]]--] = tp[i];

        // Cập nhật thứ hạng mới
        memcpy(old_rk, rk, sizeof(rk));
        int rank_count = 0;
        for (int i = 1; i <= n; ++i) {
            bool same = (old_rk[sa[i]] == old_rk[sa[i-1]]) && 
                        (old_rk[sa[i]+w] == old_rk[sa[i-1]+w]);
            rk[sa[i]] = same ? rank_count : ++rank_count;
        }

        // Nếu tất cả hậu tố đã phân biệt, dừng sớm
        if (rank_count == n) break;
        m = rank_count; // Giới hạn lại phạm vi ký tự
    }
}

Mảng Height – Độ dài tiền tố chung dài nhất

Định nghĩa

Đặt \text{LCP}(i,j) = \text{lcp}(\text{suffix}(i), \text{suffix}(j)) là độ dài tiền tố chung lớn nhất giữa hai hậu tố.

Mảng ht[] được định nghĩa như sau:

ht[i] = \text{LCP}(sa[i], sa[i-1])

Tính chất quan trọng

Bổ đề: ht[\text{rk}[i]] \ge ht[\text{rk}[i-1]] - 1

Nghĩa là: Khi xét hậu tố bắt đầu tại i, độ dài LCP với hậu tố đứng trước nó trong thứ tự từ điển sẽ không nhỏ hơn độ dài LCP của hậu tố i-1 trừ đi 1.

Thuật toán tính mảng height

Dựa vào bổ đề trên, ta có thể tính toàn bộ mảng ht[] trong thời gian tuyến tính.

int ht[MAXN];

void compute_height() {
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        if (rk[i] == 1) {
            k = 0;
            continue;
        }
        int j = sa[rk[i] - 1]; // Hậu tố liền trước trong thứ tự từ điển
        while (i + k <= n && j + k <= n && s[i+k] == s[j+k]) ++k;
        ht[rk[i]] = k;
        if (k) --k; // Giảm k để tận dụng cho bước tiếp theo
    }
}

Mã nguồn trên hoạt động hiệu quả vì biến k tổng cộng chỉ tăng tối đa n lần, do đó độ phức tạp tổng là O(n).