Suffix Array

Wiki › Thuật toán › Thuật toán xâu

huunguyen · Last updated 8, Tháng 4, 2026, 15:17

Suffix Array (SA) là mảng các chỉ số suffix của xâu $s$ , được sắp xếp theo thứ tự từ điển. Cùng với mảng LCP, đây là công cụ mạnh nhất để giải các bài toán xâu phức tạp.

Ứng dụng: Tìm chuỗi con dài nhất xuất hiện $\geq k$ lần, đếm số chuỗi con phân biệt, tìm chuỗi con chung dài nhất (LCS), so sánh từ điển.

Cài đặt — $O (N \log N)$ (Prefix Doubling)

// Xây dựng suffix array trong O(N log N)
// sa[i] = chỉ số bắt đầu của suffix thứ i theo thứ tự từ điển
// rank[i] = thứ hạng của suffix bắt đầu tại i
vector<int> suffix_array(const string& s) {
    int n = s.size();
    vector<int> sa(n), rank_(n), tmp(n);

    iota(sa.begin(), sa.end(), 0);
    for (int i = 0; i < n; i++) rank_[i] = s[i];

    for (int gap = 1; gap < n; gap <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rank_[a] != rank_[b]) return rank_[a] < rank_[b];
            int ra = a + gap < n ? rank_[a + gap] : -1;
            int rb = b + gap < n ? rank_[b + gap] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);

        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        rank_ = tmp;
    }
    return sa;
}

Mảng LCP — $O (N)$ (Kasai's Algorithm)

lcp[i] = độ dài prefix chung dài nhất giữa suffix sa[i] và sa[i-1].

vector<int> build_lcp(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank_(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank_[sa[i]] = i;

    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank_[i] > 0) {
            int j = sa[rank_[i] - 1];
            while (i + h < n && j + h < n && s[i+h] == s[j+h]) h++;
            lcp[rank_[i]] = h;
            if (h > 0) h--;
        }
    }
    return lcp;
}

Ví dụ

Với $s = "banana"$ :

$i$	Suffix	SA	LCP
0	`a`	5	0
1	`ana`	3	1
2	`anana`	1	3
3	`banana`	0	0
4	`na`	4	0
5	`nana`	2	2

Ứng dụng thường gặp

1. Số chuỗi con phân biệt:

\frac{N (N + 1)}{2} - \sum_{i = 1}^{N - 1} lcp [i]

2. Chuỗi con dài nhất xuất hiện $\geq k$ lần:

Tìm max trong sliding window kích thước $k - 1$ trên mảng LCP (dùng Sparse Table hoặc monotonic deque).

3. Chuỗi con chung dài nhất (LCS) của hai xâu $s$ và $t$ :

Nối $s + {^{'} </mi>$ '} + t$ (ký tự $ nhỏ hơn mọi ký tự). Xây SA + LCP. Kết quả là max LCP giữa hai suffix thuộc hai xâu khác nhau.

string st = s + "$" + t;
auto sa = suffix_array(st);
auto lcp = build_lcp(st, sa);

int ns = s.size(), ans = 0;
for (int i = 1; i < (int)st.size(); i++) {
    bool left_s  = (sa[i-1] < ns);
    bool right_s = (sa[i]   < ns);
    if (left_s != right_s)   // hai suffix từ hai xâu khác nhau
        ans = max(ans, lcp[i]);
}
cout << ans << "\n";

Độ phức tạp

	Độ phức tạp
Xây dựng SA	$O (N \log N)$
Xây dựng LCP	$O (N)$
RMQ trên LCP (Sparse Table)	$O (N \log N)$ build, $O (1)$ query

Khi nào dùng Suffix Array?

Bài toán liên quan đến chuỗi con và sắp xếp từ điển.
Thay thế Suffix Tree với cài đặt đơn giản hơn nhiều.
Kết hợp với Sparse Table để trả lời LCP $(i, j)$ trong $O (1)$ .

Bình luận

Không có bình luận tại thời điểm này.