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

Suffix Array

huunguyen Updated Tháng sáu 2, 2026

Suffix Array (mảng hậu tố, viết tắt SA) của một xâu $s$ độ dài $n$ là mảng chứa $n$ chỉ số khởi đầu của tất cả hậu tố (suffix) của $s$ , được sắp xếp theo thứ tự từ điển. Nói cách khác, nếu ta liệt kê mọi hậu tố rồi sắp xếp chúng, $s a [i]$ là vị trí bắt đầu của hậu tố nhỏ thứ $i$ .

Cách ngây thơ là tạo ra $n$ hậu tố rồi gọi sort so sánh trực tiếp: mỗi phép so sánh tốn $O (n)$ , tổng cộng $O (n^{2} \log n)$ — không khả thi với $n = 10^{5}$ . Kỹ thuật nhân đôi tiền tố (prefix doubling) hạ độ phức tạp xuống $O (n \log^{2} n)$ (hoặc $O (n \log n)$ nếu thay sort bằng radix sort). Kết hợp với mảng LCP (Longest Common Prefix — tiền tố chung dài nhất giữa hai hậu tố liền kề trong SA) xây bằng thuật toán Kasai trong $O (n)$ , SA trở thành công cụ mạnh nhất để giải các bài toán xâu con: đếm xâu con phân biệt, tìm xâu lặp dài nhất, tìm mẫu, so sánh từ điển hai đoạn con...

Ý tưởng / Trực giác

Vì sao "nhân đôi tiền tố" đúng?

Quan sát mấu chốt: muốn sắp xếp các hậu tố, ta sắp dần theo độ dài tiền tố ngày càng tăng $1, 2, 4, 8, \dots$ Ở mỗi vòng ta gán cho mỗi vị trí $i$ một "thứ hạng" (rank) thể hiện thứ tự từ điển của đoạn $s [i . . i + k - 1]$ (đoạn dài $k$ bắt đầu tại $i$ ).

Vòng đầu ( $k = 1$ ): rank của vị trí $i$ chính là mã ký tự $s [i]$ . Hai vị trí cùng rank khi và chỉ khi cùng ký tự.
Bước nhân đôi ( $k \to 2 k$ ): một đoạn dài $2 k$ tại $i$ = đoạn dài $k$ tại $i$ ghép với đoạn dài $k$ tại $i + k$ . Vì ta đã biết thứ hạng của mọi đoạn dài $k$ từ vòng trước, đoạn dài $2 k$ tại $i$ được mã hoá gọn bằng cặp $(r a n k [i], r a n k [i + k])$ . So sánh hai đoạn dài $2 k$ chỉ còn là so sánh hai cặp số nguyên — tốn $O (1)$ thay vì $O (k)$ .

Sắp xếp các hậu tố theo cặp đó rồi gán lại rank mới. Sau $⌈ \log_{2} n ⌉$ vòng, $k \geq n$ nên rank đã phân biệt mọi hậu tố hoàn toàn — đó chính là thứ tự từ điển cuối cùng. Đây là tư tưởng giống hệt đổi bài toán so sánh xâu dài thành so sánh cặp số mà ta cập nhật quy nạp.

Vì sao thuật toán Kasai xây LCP trong $O (n)$ ?

$l c p [i]$ = độ dài tiền tố chung dài nhất giữa hai hậu tố liền kề trong SA, tức $s a [i]$ và $s a [i - 1]$ . Kasai duyệt các hậu tố theo thứ tự vị trí gốc trong xâu ( $i = 0, 1, \dots, n - 1$ ), không theo thứ tự SA. Tính chất then chốt:

Nếu hậu tố tại $i$ có LCP với hậu tố đứng trước nó (trong SA) bằng $h$ , thì hậu tố tại $i + 1$ (bỏ ký tự đầu) có LCP với hậu tố đứng trước nó ít nhất $h - 1$ .

Trực giác: bỏ đi ký tự đầu của cả hai hậu tố thì tiền tố chung chỉ ngắn đi nhiều nhất 1. Nhờ đó biến đếm $h$ chỉ giảm tối đa 1 mỗi bước và mỗi lần tăng đều làm $h$ tiến lên; tổng số lần tăng trên toàn bộ thuật toán không vượt quá $2 n$ , nên tổng chi phí là $O (n)$ (lập luận khấu hao giống two pointers).

Ví dụ chạy tay

Lấy $s = "banana"$ , $n = 6$ . Các hậu tố (kèm chỉ số bắt đầu, đánh số từ 0):

i : 0      1      2      3     4    5
    banana anana  nana   ana   na   a

Sắp theo thứ tự từ điển (so sánh trực tiếp cho dễ hình dung):

thứ tự  sa[i]  hậu tố
  0       5    a          <- nhỏ nhất
  1       3    ana
  2       1    anana
  3       0    banana
  4       4    na
  5       2    nana

Vậy $s a = [5, 3, 1, 0, 4, 2]$ .

Tính LCP giữa các cặp liền kề (so từng ký tự):

        hậu tố trước     hậu tố sau     tiền tố chung   lcp
i=1 :   a          vs   ana            ""        ->  0
i=2 :   ana        vs   anana          "ana"     ->  3
i=3 :   anana      vs   banana         ""        ->  0
i=4 :   banana     vs   na             ""        ->  0
i=5 :   na         vs   nana           "na"      ->  2

Quy ước $l c p [0] = 0$ (không có hậu tố trước). Bảng tổng hợp:

thứ tự $i$	$s a [i]$	hậu tố	$l c p [i]$
0	5	`a`	0
1	3	`ana`	0
2	1	`anana`	3
3	0	`banana`	0
4	4	`na`	0
5	2	`nana`	2

Minh hoạ một bước nhân đôi (vòng $k = 1 \to 2$ ). Rank ban đầu theo ký tự ( $a = 0, b = 1, n = 13$ , nhưng ở đây chỉ cần thứ tự tương đối $a < b < n$ , dùng $a = 0, b = 1, n = 2$ ):

vị trí i :   0   1   2   3   4   5
s[i]     :   b   a   n   a   n   a
rank (k=1):  1   0   2   0   2   0

Tạo cặp $(r a n k [i], r a n k [i + 1])$ (với $i + 1 \geq n$ dùng $- 1$ ):

i        :   0       1       2       3       4       5
cặp k=2  : (1,0)   (0,2)   (2,0)   (0,2)   (2,-1)  (0,-1)
                            ^^^ đoạn "na" tại i=2,4 cùng cặp (2,0)

Sắp các vị trí theo cặp rồi gán rank mới: các đoạn dài 2 đã được phân lớp đúng từ điển. Lặp tiếp tới khi $k \geq n$ là xong.

Cài đặt

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

// Xây suffix array trong O(n log^2 n) bằng prefix doubling.
// Trả về sa: sa[i] = chỉ số bắt đầu của hậu tố nhỏ thứ i theo từ điển.
vector<int> suffix_array(const string& s) {
    int n = s.size();
    vector<int> sa(n), rnk(n), tmp(n);

    iota(sa.begin(), sa.end(), 0);          // sa = [0,1,...,n-1]
    for (int i = 0; i < n; i++) rnk[i] = s[i];  // rank ban đầu = mã ký tự

    for (int gap = 1; gap < n; gap <<= 1) {
        // So sánh hai hậu tố a, b dựa trên cặp (rnk[a], rnk[a+gap])
        auto cmp = [&](int a, int b) {
            if (rnk[a] != rnk[b]) return rnk[a] < rnk[b];
            int ra = (a + gap < n) ? rnk[a + gap] : -1;  // ngoài biên -> -1 (nhỏ nhất)
            int rb = (b + gap < n) ? rnk[b + gap] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);

        // Gán lại rank: hai hậu tố BẰNG nhau theo cmp mới giữ cùng rank
        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);
        rnk = tmp;

        if (rnk[sa[n - 1]] == n - 1) break;  // mọi rank đã phân biệt -> dừng sớm
    }
    return sa;
}

// Mảng LCP bằng thuật toán Kasai trong O(n).
// lcp[i] = LCP(hậu tố sa[i], hậu tố sa[i-1]); lcp[0] = 0.
vector<int> build_lcp(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rnk(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rnk[sa[i]] = i;   // nghịch đảo của sa

    int h = 0;  // giá trị LCP hiện tại, chỉ giảm tối đa 1 mỗi bước
    for (int i = 0; i < n; i++) {
        if (rnk[i] > 0) {
            int j = sa[rnk[i] - 1];               // hậu tố đứng ngay trước i trong SA
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
            lcp[rnk[i]] = h;
            if (h > 0) h--;                       // sang i+1: LCP giảm tối đa 1
        } else {
            h = 0;
        }
    }
    return lcp;
}

Phiên bản Python (ngắn, dùng cho $n$ vừa phải):

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rnk = [ord(c) for c in s]
    gap = 1
    while gap < n:
        def key(i):
            return (rnk[i], rnk[i + gap] if i + gap < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]))
        rnk = tmp
        if rnk[sa[-1]] == n - 1:
            break
        gap <<= 1
    return sa

Ứng dụng mẫu

1. Đếm số xâu con phân biệt. Tổng số xâu con (kể cả trùng) là $\frac{n (n + 1)}{2}$ . Mỗi $l c p [i]$ đếm số xâu con bị lặp lại giữa hậu tố $s a [i]$ và $s a [i - 1]$ nên phải trừ đi:

$số xâu con phân biệt = \frac{n (n + 1)}{2} - \sum_{i = 1}^{n - 1} l c p [i] .$

2. Xâu con lặp dài nhất (xuất hiện $\geq 2$ lần): chính là ${max}_{i} l c p [i]$ ; vị trí đạt max cho ta đoạn xâu cần in.

3. Tìm mẫu (pattern matching). Vì các hậu tố trong SA đã sắp từ điển, mọi hậu tố có mẫu $p$ làm tiền tố nằm thành một đoạn liên tiếp trong SA. Dùng nhị phân tìm biên trái/phải đoạn đó, mỗi lần so sánh tốn $O (| p |)$ , tổng $O (| p | \log n)$ .

// Trả về true nếu p là xâu con của s; sa là suffix array của s.
bool contains(const string& s, const vector<int>& sa, const string& p) {
    int lo = 0, hi = sa.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        // so sánh p với tiền tố của hậu tố sa[mid]
        int c = s.compare(sa[mid], p.size(), p);  // -1/0/1
        if (c < 0) lo = mid + 1; else hi = mid;
    }
    return lo < (int)sa.size() &&
           s.compare(sa[lo], p.size(), p) == 0;
}

4. Xâu con chung dài nhất (LCS) của $s$ và $t$ . Nối $s + \# + t$ với ký tự ngăn cách # nhỏ hơn mọi ký tự và không xuất hiện trong cả hai. Xây SA + LCP, đáp án là $l c p [i]$ lớn nhất giữa hai hậu tố 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);   // hậu tố trước thuộc s?
    bool right_s = (sa[i]     < ns);   // hậu tố sau  thuộc s?
    if (left_s != right_s)             // đúng khi hai hậu tố thuộc hai xâu khác nhau
        ans = max(ans, lcp[i]);
}

Độ phức tạp

Thao tác	Thời gian	Bộ nhớ
Xây SA (prefix doubling + `sort`)	$O (n \log^{2} n)$	$O (n)$
Xây SA (thay bằng radix sort)	$O (n \log n)$	$O (n)$
Xây LCP (Kasai)	$O (n)$	$O (n)$
RMQ trên LCP (Sparse Table)	$O (n \log n)$ build, $O (1)$ truy vấn	$O (n \log n)$

Vì sao $O (n \log^{2} n)$ ? Có $\log n$ vòng nhân đôi (mỗi vòng $k$ tăng gấp đôi tới khi $\geq n$ ); mỗi vòng gọi sort tốn $O (n \log n)$ . Nhân lại được $O (n \log^{2} n)$ . Nếu thay sort so sánh bằng đếm phân phối (radix sort) hai khoá thì mỗi vòng còn $O (n)$ , tổng $O (n \log n)$ .

Vì sao LCP là $O (n)$ ? Biến $h$ chỉ giảm tối đa 1 mỗi bước ngoài, mà $0 \leq h \leq n$ , nên tổng số lần h++ trên cả vòng không quá $2 n$ — chi phí khấu hao tuyến tính.

Bộ nhớ: các mảng sa, rnk, tmp, lcp đều cỡ $n$ nên $O (n)$ ; Sparse Table thì $O (n \log n)$ .

⚠️ Lỗi thường gặp

Quên ràng buộc biên khi $i + g a p \geq n$ / $i + h \geq n$ . Hậu tố ngắn hơn phải được coi là nhỏ hơn về từ điển. Trong cmp phải dùng giá trị canh -1 cho phần vượt biên; trong Kasai phải có điều kiện i + h < n && j + h < n trước khi so s[i+h] == s[j+h], nếu không sẽ đọc ngoài mảng (undefined behavior / RE).
Ký tự ngăn cách trong bài LCS/nối xâu chọn sai. Ký tự # phải nhỏ hơn mọi ký tự thật và không xuất hiện trong dữ liệu, nếu không hai hậu tố ở hai bên có thể "khớp xuyên qua" dấu ngăn, cho LCP sai (lớn hơn thực tế). Với chữ thường a-z, dùng ký tự có mã nhỏ hơn 'a' (vd '#', '$').
Tràn số khi cộng dồn LCP. Số xâu con phân biệt là $\frac{n (n + 1)}{2} - \sum l c p [i]$ ; với $n = 10^{5}$ thì $\frac{n (n + 1)}{2} \approx 5 \times 10^{9}$ , vượt int. Phải dùng long long. Tương tự các bài như wineparty đếm số cặp $(\binom{n}{2})$ và tích $a_{i} a_{j}$ tới $10^{18}$ đều cần long long.
Lẫn lộn sa và rank (mảng nghịch đảo). sa[i] = vị trí của hậu tố nhỏ thứ $i$ ; rnk[p] = hạng từ điển của hậu tố bắt đầu tại $p$ . Chúng là nghịch đảo của nhau ( $r n k [s a [i]] = i$ ). Dùng nhầm cái này cho cái kia là lỗi rất hay gặp và khó debug.
Quên gán $l c p [0] = 0$ rồi cộng nhầm. $l c p [0]$ không có hậu tố đứng trước; nếu vô tình để giá trị rác và đưa vào tổng/max sẽ sai kết quả.
Tưởng nhị phân tìm mẫu là $O (\log n)$ . Mỗi lần so sánh trong nhị phân tốn tới $O (| p |)$ vì phải so từng ký tự, nên độ phức tạp đúng là $O (| p | \log n)$ mỗi truy vấn, không phải $O (\log n)$ . Với tổng độ dài mẫu lớn cần lưu ý chi phí này.
sort không ổn định không phải vấn đề, nhưng quên break khi rank đã phân biệt khiến chạy thừa nhiều vòng. Thêm if (rnk[sa[n-1]] == n-1) break; để dừng sớm khi mọi rank đã khác nhau.

Biến thể / Mở rộng

Radix sort hai khoá thay sort: hạ xây dựng xuống $O (n \log n)$ , cần thiết khi $n$ lớn ( $\geq 3 \times 10^{5}$ ).
Thuật toán SA-IS xây SA trong $O (n)$ tuyến tính thuần — cài đặt phức tạp, dùng khi cần tối ưu hằng số.
LCP + Sparse Table cho phép truy vấn $LCP (i, j)$ giữa hai hậu tố bất kỳ trong $O (1)$ (RMQ trên đoạn $l c p$ ). Đây là chìa khoá cho các bài so sánh hai đoạn con tuỳ ý.
Nhóm hậu tố theo ngưỡng LCP (gộp các hậu tố có LCP $\geq r$ thành nhóm bằng union-find khi tăng dần $r$ ) là kỹ thuật trong wineparty.
Quan hệ với Suffix Automaton / Suffix Tree: SA + LCP cho cùng sức mạnh nhưng cài đặt đơn giản, tốn ít bộ nhớ hơn Suffix Tree.

Bài tập luyện

Mảng Hậu Tố Nghịch (invsfxarr) — (Nâng cao) Cho trước SA, dựng lại một xâu hợp lệ; bài "ngược" giúp nắm chắc cấu trúc và tính chất thứ tự của mảng hậu tố.
Vị Trí Mẫu (patpos) — (Kỳ cựu) Tìm vị trí xuất hiện đầu tiên của nhiều mẫu bằng nhị phân trên SA — luyện đúng kỹ thuật pattern matching $O (| p | \log n)$ .
Tìm Mẫu (findpat) — (Kỳ cựu) Kiểm tra mẫu có là xâu con hay không cho hàng loạt truy vấn; củng cố nhị phân tìm đoạn hậu tố có cùng tiền tố.
Xâu Con Lặp Lại (repsubstr) — (Chuyên gia) Xâu con lặp dài nhất chính là $max l c p [i]$ — ứng dụng trực tiếp nhất của mảng LCP.
Xâu Con Phân Biệt (distsubstr) — (Chuyên gia) Đếm số xâu con phân biệt bằng công thức $\frac{n (n + 1)}{2} - \sum l c p [i]$ ; nhớ dùng long long.
Tiệc Phép Thuật (wineparty) — (Chuyên gia) Nhóm các hậu tố theo ngưỡng LCP bằng union-find khi giảm dần $r$ , kết hợp truy vết tích lớn nhất — bài tổng hợp SA + LCP + cấu trúc dữ liệu.