Wiki › Thuật toán › Thuật toán xâu › Suffix Tree (thuật toán Ukkonen)

Suffix Tree (thuật toán Ukkonen)

Cây hậu tố nén chứa mọi xâu con của s trong O(n) đỉnh, dựng online bằng thuật toán Ukkonen trong O(n). Ứng dụng: tìm mẫu, đếm xâu con phân biệt, xâu con lặp dài nhất, LCS qua cây tổng quát.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 21 phút 1 lượt xem

Cây hậu tố (suffix tree) của xâu s độ dài n là cây chứa mọi hậu tố của s, trong đó mỗi xâu con của s ứng với đúng một "điểm" trên cây (tại một đỉnh hoặc giữa một cạnh). Nhờ đó các câu hỏi như "mẫu p có xuất hiện không, bao nhiêu lần", "có bao nhiêu xâu con phân biệt", "xâu con lặp dài nhất là gì" đều trả lời được bằng một lần đi trên cây. Cây trie thô chứa mọi hậu tố có thể tới O(n2) đỉnh, còn cây hậu tố nén chỉ có O(n) đỉnh, và thuật toán Ukkonen dựng nó online (thêm từng ký tự) trong O(n) thay vì O(n2).

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

Từ suffix trie đến cây hậu tố nén

Cách ngây thơ: chèn lần lượt mọi hậu tố s[i..n] vào một trie. Ta được suffix trie: mỗi đường đi từ gốc đọc ra đúng một xâu con, nên số đỉnh bằng số xâu con phân biệt cộng 1, tức có thể tới ≈n2/2 đỉnh (xâu abcd...z không lặp ký tự nào là ví dụ xấu nhất).

Quan sát: phần lớn đỉnh của trie chỉ có một con, chúng chỉ nằm trên một "ống" không rẽ nhánh. Nén mỗi chuỗi đỉnh một con thành một cạnh mang nhãn là cả đoạn xâu, ta được cây hậu tố nén (compressed suffix tree), thường gọi tắt là cây hậu tố. Sau khi nén:

  • Mỗi đỉnh trong (trừ gốc) có ít nhất 2 con, vì đó là chỗ các hậu tố "tách đường".
  • Nếu mỗi hậu tố kết thúc ở một lá thì có đúng n lá, nên số đỉnh trong ≤n−1 và tổng số đỉnh ≤2n.
  • Nhãn cạnh không lưu thành xâu (tổng độ dài vẫn có thể là O(n2)) mà lưu bằng hai chỉ số [l,r] trỏ vào s, nên bộ nhớ là O(n).

Ví dụ với s=abab: trie hậu tố có 8 đỉnh (7 xâu con phân biệt và gốc), nhưng nó chỉ là hai "ống" nên khi nén còn đúng hai cạnh:

dot
digraph {
  rankdir=LR;
  node [shape=circle, width=0.3, label=""];
  r [label="gốc", shape=box];
  r -> a1 [label="a"]; a1 -> a2 [label="b"]; a2 -> a3 [label="a"]; a3 -> a4 [label="b"];
  r -> b1 [label="b"]; b1 -> b2 [label="a"]; b2 -> b3 [label="b"];
  r2 [label="gốc", shape=box];
  l1 [shape=box, label="1"]; l2 [shape=box, label="2"];
  r2 -> l1 [label="abab"];
  r2 -> l2 [label="bab"];
}

Bên trái là suffix trie, bên phải là cây đã nén. Để ý: hậu tố ab và b không kết thúc ở lá mà nằm lơ lửng giữa cạnh, vì chúng là tiền tố của hậu tố khác. Cây như vậy gọi là cây ẩn (implicit suffix tree). Để mọi hậu tố đều thành lá, ta nối thêm một ký tự kết thúc $ không xuất hiện trong s: không hậu tố nào của abab$ là tiền tố của hậu tố khác.

Mỗi xâu con là một điểm trên cây

Xâu t là xâu con của s khi và chỉ khi t là tiền tố của một hậu tố nào đó, tức đọc được từ gốc đi xuống. Điểm dừng sau khi đọc t gọi là locus của t. Vì cây là trie đã nén, mỗi xâu con có đúng một locus. Hệ quả trực tiếp:

  • Tìm mẫu p: đi từ gốc theo các ký tự của p, mất O(|p|).
  • Số lần xuất hiện của p = số lá trong cây con dưới locus của p (mỗi lá là một vị trí bắt đầu).
  • Số xâu con phân biệt = số điểm trên cây = tổng độ dài các cạnh (không tính ký tự $).
  • Xâu con lặp dài nhất = đỉnh trong có độ sâu xâu (string depth, tổng độ dài nhãn từ gốc) lớn nhất, vì đỉnh trong có ít nhất 2 lá bên dưới tức xâu xuất hiện ít nhất 2 lần.
Thuật toán Ukkonen: thêm từng ký tự

Ukkonen xử lý s từ trái sang phải. Sau pha i (đã đọc s[1..i]), ta có cây ẩn của s[1..i]. Thêm ký tự c=s[i+1] nghĩa là kéo dài mọi hậu tố s[j..i] thêm c. Làm thô thì mỗi pha tốn O(i) hậu tố, tổng O(n2) (thậm chí O(n3) nếu đi lại từ gốc). Ba mẹo biến nó thành O(n):

1. Lá có "đuôi mở" (open end). Một khi là lá thì mãi là lá: lá chỉ việc kéo dài thêm c. Ta cho mọi cạnh lá có điểm cuối là một biến chung leafEnd. Đầu mỗi pha tăng leafEnd lên 1 là mọi lá tự dài ra trong O(1). Đây là luật 1.

2. Luật 3 dừng cả pha. Xét các hậu tố chưa phải lá theo thứ tự dài đến ngắn. Với mỗi hậu tố t:

  • Nếu sau locus của t chưa có ký tự c: tạo lá mới (nếu locus nằm giữa cạnh thì tách cạnh tạo đỉnh trong mới). Đây là luật 2.
  • Nếu sau locus đã có ký tự c: tc đã nằm trong cây, và mọi hậu tố ngắn hơn của tc cũng vậy (hậu tố của xâu con vẫn là xâu con). Ta dừng pha ngay. Đây là luật 3.

Biến remainder đếm số hậu tố đang "nợ" (chưa được chèn tường minh). Mỗi pha remainder tăng 1; mỗi lần áp luật 2 thì giảm 1; gặp luật 3 thì để dành sang pha sau.

3. Điểm hoạt động (active point) và suffix link. Thay vì đi từ gốc tìm locus của hậu tố cần chèn, ta lưu bộ ba active point = (activeNode, activeEdge, activeLength): locus nằm trên cạnh bắt đầu bằng ký tự activeEdge ra khỏi activeNode, cách activeNode đúng activeLength ký tự. Sau khi chèn xong hậu tố xα (với x là ký tự đầu), hậu tố kế tiếp cần chèn là α. Để nhảy nhanh từ locus của xα sang locus của α:

  • Mỗi đỉnh trong v ứng với xâu xα có suffix link trỏ tới đỉnh ứng với α. Nếu activeNode khác gốc, chỉ cần activeNode = link[activeNode], giữ nguyên cạnh và độ dài.
  • Nếu activeNode là gốc thì bỏ ký tự đầu: activeLength--, activeEdge dời sang phải một vị trí.
  • Khi activeLength dài hơn cạnh hiện tại, ta nhảy qua cả cạnh (skip/count) chỉ bằng phép trừ độ dài, không so từng ký tự.

Suffix link của đỉnh trong mới được gán ngay trong pha đó: đỉnh tách ra trước sẽ trỏ tới đỉnh tách ra sau (hoặc tới activeNode khi pha kết thúc bằng luật 3 hay khi lá mới gắn thẳng vào một đỉnh có sẵn).

Ví dụ chạy tay: dựng cây cho abcabx$

Đánh số vị trí từ 1. Ký hiệu active point là (đỉnh, cạnh, độ dài).

Pha Ký tự Việc xảy ra Active point sau pha remainder
1 a Gốc chưa có cạnh a: luật 2, tạo lá a (gốc, -, 0) 0
2 b Luật 1: lá thành ab. Gốc chưa có b: tạo lá b (gốc, -, 0) 0
3 c Luật 1: abc, bc. Tạo lá c (gốc, -, 0) 0
4 a Luật 1: abca, bca, ca. Hậu tố a đã có (đầu cạnh abca): luật 3, dừng (gốc, a, 1) 1
5 b Luật 1: abcab, bcab, cab. Sau a trên cạnh là b: luật 3, dừng (gốc, a, 2) 2
6 x Nợ 3 hậu tố abx, bx, x, xem bên dưới (gốc, -, 0) 0
7 $ Gốc chưa có $: tạo lá $ (gốc, -, 0) 0

Ở pha 4 và 5, cây không đổi hình dạng (chỉ có lá tự dài ra), ta chỉ "ghi nợ" bằng cách tăng remainder và activeLength. Pha 6 là lúc trả nợ:

  1. remainder = 3, locus là (gốc, a, 2), tức sau ab trên cạnh abcabx. Ký tự kế trên cạnh là c khác x: tách cạnh tại ab, tạo đỉnh trong u = ab, gắn lá x vào u. remainder = 2. Đang ở gốc nên activeLength = 1, activeEdge chuyển sang b.
  2. Locus (gốc, b, 1), sau b là c khác x: tách cạnh tạo đỉnh w = b, gắn lá x. Gán suffix link u→w (vì ab bỏ ký tự đầu là b). remainder = 1, activeLength = 0.
  3. Locus là gốc, gốc chưa có cạnh x: tạo lá x. Gán link w→ gốc. remainder = 0.

Cây cuối cùng (lá ghi vị trí bắt đầu của hậu tố, nét đứt là suffix link):

dot
digraph {
  node [shape=circle, width=0.35, label=""];
  root [label="gốc", shape=box];
  u [label="ab"]; w [label="b"];
  l1 [shape=box, label="1"]; l2 [shape=box, label="2"]; l3 [shape=box, label="3"];
  l4 [shape=box, label="4"]; l5 [shape=box, label="5"]; l6 [shape=box, label="6"]; l7 [shape=box, label="7"];
  root -> l7 [label="$"];
  root -> u [label="ab"];
  u -> l1 [label="cabx$"];
  u -> l4 [label="x$"];
  root -> w [label="b"];
  w -> l2 [label="cabx$"];
  w -> l5 [label="x$"];
  root -> l3 [label="cabx$"];
  root -> l6 [label="x$"];
  u -> w [style=dashed, color=gray, constraint=false];
  w -> root [style=dashed, color=gray, constraint=false];
}

Kiểm tra các ứng dụng trên cây này:

  • Số xâu con phân biệt của abcabx: 9 cạnh có độ dài $ 1, ab 2, cabx$ 5, x$ 2, b 1, cabx$ 5, x$ 2, cabx$ 5, x$ 2, tổng 25. Mỗi cạnh trong 7 cạnh lá kết thúc bằng $ nên trừ 7, còn 18. Đối chiếu: có 6·72=21 cách chọn đoạn, trùng nhau là a, b, ab (mỗi xâu xuất hiện 2 lần), nên còn 21−3=18. Khớp.
  • Xâu con lặp dài nhất: đỉnh trong sâu nhất là ab (độ sâu 2).
  • Tìm bca: gốc, cạnh b đến w, cạnh cabx$ khớp ca: có. Dưới locus có 1 lá (vị trí 2) nên xuất hiện 1 lần.

Cài đặt

Code dưới đây dựng cây bằng Ukkonen cho xâu chữ thường, thêm $ ở cuối, rồi in số xâu con phân biệt và xâu con lặp dài nhất (in -1 nếu không có). Mỗi đỉnh v lưu nhãn cạnh đi vào nó là text[st[v]..en[v]]; lá có en[v] = LEAF nghĩa là "kết thúc tại leafEnd".

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

// Ukkonen's online suffix tree construction, O(n * |alphabet|).
// Characters 'a'..'z' map to 0..25, the terminator '$' maps to 26.
struct SuffixTree {
    static const int ALPHA = 27;
    static const int LEAF = INT_MAX;   // "open end": the edge grows with the text
    vector<array<int, ALPHA>> nxt;     // children, -1 = none
    vector<int> st, en, link;          // edge label = text[st[v] .. en[v]]
    vector<int> text;
    int leafEnd = -1;                  // shared end of every leaf edge
    int actNode = 0, actEdge = 0, actLen = 0, remainder = 0;

    SuffixTree() { newNode(-1, -1); }  // node 0 = root

    int newNode(int s, int e) {
        array<int, ALPHA> a; a.fill(-1);
        nxt.push_back(a); st.push_back(s); en.push_back(e); link.push_back(0);
        return (int)st.size() - 1;
    }
    int edgeLen(int v) const { return (en[v] == LEAF ? leafEnd : en[v]) - st[v] + 1; }

    void extend(int c) {
        text.push_back(c);
        int i = (int)text.size() - 1;
        leafEnd = i;        // rule 1: all leaves grow by one character for free
        remainder++;        // one more suffix waits to be inserted
        int lastNew = -1;   // internal node created in this phase, waiting for its suffix link
        while (remainder > 0) {
            if (actLen == 0) actEdge = i;
            int ch = text[actEdge];
            int nx = nxt[actNode][ch];
            if (nx == -1) {
                // rule 2: no edge starting with ch, hang a new leaf at actNode
                nxt[actNode][ch] = newNode(i, LEAF);
                if (lastNew != -1) { link[lastNew] = actNode; lastNew = -1; }
            } else {
                int L = edgeLen(nx);
                if (actLen >= L) {          // skip/count: jump over a whole edge
                    actEdge += L; actLen -= L; actNode = nx;
                    continue;
                }
                if (text[st[nx] + actLen] == c) {
                    // rule 3: the suffix is already in the tree, stop this phase
                    if (lastNew != -1) { link[lastNew] = actNode; lastNew = -1; }
                    actLen++;
                    break;
                }
                // rule 2 inside an edge: split it
                int split = newNode(st[nx], st[nx] + actLen - 1);
                nxt[actNode][ch] = split;
                nxt[split][c] = newNode(i, LEAF);
                st[nx] += actLen;
                nxt[split][text[st[nx]]] = nx;
                if (lastNew != -1) link[lastNew] = split;
                lastNew = split;
            }
            remainder--;    // one suffix inserted
            if (actNode == 0 && actLen > 0) {
                actLen--;
                actEdge = i - remainder + 1;   // next suffix starts one position later
            } else if (actNode != 0) {
                actNode = link[actNode];        // follow suffix link
            }
        }
    }
};

int main() {
    string s;
    cin >> s;
    SuffixTree t;
    for (char ch : s) t.extend(ch - 'a');
    t.extend(26);   // '$' turns every suffix into a leaf

    // Every distinct substring is exactly one point on some edge.
    // Each leaf edge ends with '$', which must not be counted.
    long long distinct = 0;
    int leaves = 0;
    for (int v = 1; v < (int)t.st.size(); v++) {
        distinct += t.edgeLen(v);
        if (t.en[v] == SuffixTree::LEAF) leaves++;
    }
    distinct -= leaves;

    // Longest repeated substring = deepest internal node (string depth).
    vector<int> depth(t.st.size(), 0);
    int best = 0, bestEnd = -1;
    vector<int> stk = {0};
    while (!stk.empty()) {
        int v = stk.back(); stk.pop_back();
        for (int c = 0; c < SuffixTree::ALPHA; c++) {
            int u = t.nxt[v][c];
            if (u == -1 || t.en[u] == SuffixTree::LEAF) continue;   // skip leaves
            depth[u] = depth[v] + t.edgeLen(u);
            if (depth[u] > best) { best = depth[u]; bestEnd = t.en[u]; }
            stk.push_back(u);
        }
    }
    cout << distinct << "\n";
    cout << (best == 0 ? string("-1") : s.substr(bestEnd - best + 1, best)) << "\n";
}
Python
import sys

LEAF = float("inf")  # open end of a leaf edge


class SuffixTree:
    """Ukkonen's online construction. Children are stored in dicts."""

    def __init__(self):
        self.nxt = [{}]          # node 0 = root
        self.st = [-1]
        self.en = [-1]
        self.link = [0]
        self.text = []
        self.leaf_end = -1
        self.act_node = self.act_edge = self.act_len = self.remainder = 0

    def new_node(self, s, e):
        self.nxt.append({}); self.st.append(s); self.en.append(e); self.link.append(0)
        return len(self.st) - 1

    def edge_len(self, v):
        e = self.leaf_end if self.en[v] == LEAF else self.en[v]
        return e - self.st[v] + 1

    def extend(self, c):
        text = self.text
        text.append(c)
        i = len(text) - 1
        self.leaf_end = i            # rule 1: leaves grow for free
        self.remainder += 1
        last_new = -1
        while self.remainder > 0:
            if self.act_len == 0:
                self.act_edge = i
            ch = text[self.act_edge]
            nx = self.nxt[self.act_node].get(ch, -1)
            if nx == -1:             # rule 2: new leaf
                self.nxt[self.act_node][ch] = self.new_node(i, LEAF)
                if last_new != -1:
                    self.link[last_new] = self.act_node
                    last_new = -1
            else:
                L = self.edge_len(nx)
                if self.act_len >= L:    # skip/count
                    self.act_edge += L
                    self.act_len -= L
                    self.act_node = nx
                    continue
                if text[self.st[nx] + self.act_len] == c:   # rule 3: stop
                    if last_new != -1:
                        self.link[last_new] = self.act_node
                    self.act_len += 1
                    break
                split = self.new_node(self.st[nx], self.st[nx] + self.act_len - 1)
                self.nxt[self.act_node][ch] = split
                self.nxt[split][c] = self.new_node(i, LEAF)
                self.st[nx] += self.act_len
                self.nxt[split][text[self.st[nx]]] = nx
                if last_new != -1:
                    self.link[last_new] = split
                last_new = split
            self.remainder -= 1
            if self.act_node == 0 and self.act_len > 0:
                self.act_len -= 1
                self.act_edge = i - self.remainder + 1
            elif self.act_node != 0:
                self.act_node = self.link[self.act_node]


def main():
    s = sys.stdin.readline().strip()
    t = SuffixTree()
    for ch in s:
        t.extend(ch)
    t.extend("$")                # terminator, not in the alphabet
    distinct = 0
    for v in range(1, len(t.st)):
        distinct += t.edge_len(v)
        if t.en[v] == LEAF:
            distinct -= 1        # drop the trailing '$' of each leaf edge
    # longest repeated substring = deepest internal node
    best, best_end = 0, -1
    stack = [(0, 0)]
    while stack:
        v, d = stack.pop()
        for u in t.nxt[v].values():
            if t.en[u] == LEAF:
                continue
            du = d + t.edge_len(u)
            if du > best:
                best, best_end = du, t.en[u]
            stack.append((u, du))
    print(distinct)
    print(s[best_end - best + 1: best_end + 1] if best else -1)


main()

Chạy thử:

Input Output
abcabx 18
ab
cabababc 25
abab
abaa 8
a

Cả hai bản đã được đối chiếu với lời giải trâu (liệt kê mọi xâu con bằng set) trên hàng nghìn xâu ngẫu nhiên. Bản C++ xử lý xâu n=105 trong khoảng 0.05 giây.

Để tìm mẫu p, đi từ gốc: tại đỉnh v chọn con nxt[v][p[k]], so lần lượt các ký tự trên nhãn cạnh với p; lệch một ký tự là không có, đi hết p là có. Để đếm số lần xuất hiện, tính trước số lá trong mỗi cây con bằng một lần DFS rồi tra tại đỉnh ngay dưới locus.

Độ phức tạp

  • Thời gian O(n·σ) với cài đặt mảng con cỡ σ (khởi tạo mảng tốn σ mỗi đỉnh), hoặc O(nlogσ) với map. Phần thuật toán Ukkonen chỉ tốn O(n) bước:
    • Mỗi lần áp luật 2 giảm remainder đi 1, mà remainder chỉ tăng đúng 1 mỗi pha, nên tổng số lần chèn tường minh ≤n. Luật 3 xảy ra tối đa một lần mỗi pha.
    • Bước skip/count: mỗi lần nhảy qua một cạnh, activeLength giảm ít nhất 1. activeLength chỉ tăng 1 ở luật 3 (tối đa một lần mỗi pha), nên tổng số lần nhảy cạnh là O(n). Đi theo suffix link không làm tăng activeLength.
  • Bộ nhớ O(n·σ): tối đa 2n đỉnh (với n tính cả $), mỗi đỉnh lưu 3 số nguyên và mảng σ con. Với n=105 và σ=27 là khoảng 2·105·27·4≈22 MB.
  • Đếm xâu con phân biệt, tìm xâu con lặp dài nhất: một lần duyệt cây, O(n·σ). Tìm mẫu: O(|p|).

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

  • Quên ký tự kết thúc $. Cây khi đó là cây ẩn: một số hậu tố nằm giữa cạnh, không có lá riêng. Triệu chứng: đếm số lần xuất hiện bằng số lá bị thiếu, xâu con lặp dài nhất sai (với aa, cây ẩn chỉ có một cạnh aa, không có đỉnh trong nào nên báo "không có", trong khi đáp án là a). Cách tránh: luôn extend('$') sau cùng, với $ nằm ngoài bảng chữ cái.
  • Quên trừ ký tự $ khi đếm. Mỗi cạnh lá kết thúc bằng $; tổng độ dài cạnh phải trừ đi số lá. Quên bước này thì đáp án dư đúng n+1.
  • Lưu nhãn cạnh bằng string. Tổng độ dài các nhãn có thể là Θ(n2) (cạnh lá từ gốc dài gần n), cùng với việc cập nhật lá mỗi pha thì thành O(n2) thời gian và bộ nhớ. Luôn lưu cặp chỉ số và dùng một biến leafEnd chung cho mọi lá.
  • Thiếu bước skip/count (if (actLen >= edgeLen(nx))). Khi activeLength dài hơn cạnh, phép so text[st[nx] + actLen] đọc nhầm sang ký tự không thuộc cạnh. Triệu chứng: sai lẻ tẻ chỉ trên xâu có nhiều lặp như abababab.
  • Cập nhật sai activeEdge ở gốc. Sau khi chèn xong một hậu tố tại gốc, hậu tố kế tiếp bắt đầu muộn hơn một vị trí: actEdge = i - remainder + 1, tính sau khi đã giảm remainder. Đặt lệnh này trước remainder-- sẽ lệch một ký tự.
  • Quên gán suffix link cho đỉnh vừa tách khi pha kết thúc bằng luật 3 hoặc khi lá mới gắn thẳng vào một đỉnh có sẵn. Link mặc định trỏ về gốc, nên lần sau nhảy theo link sẽ đứng sai chỗ (vẫn giữ activeEdge, activeLength của đỉnh cũ) và cây bị dựng sai. Cách tránh: mọi nhánh của vòng lặp đều phải xử lý lastNew.
  • Dùng int cho số xâu con phân biệt. Đáp số tới n(n+1)2≈5·109 với n=105: dùng long long.
  • Mảng con cỡ σ khi n lớn. Với n=106 thì 2·106·27 số int là khoảng 216 MB, vượt giới hạn. Đổi sang map, danh sách cạnh, hoặc dùng Suffix Array / Suffix Automaton.

Liên hệ với Suffix Array và Suffix Automaton

Cây hậu tố và mảng hậu tố + LCP

Duyệt DFS cây hậu tố của s$, đi các cạnh con theo thứ tự ký tự tăng dần ($ nhỏ nhất). Thứ tự gặp các lá chính là mảng hậu tố (suffix array). Với abcabx$ thứ tự lá là 7,1,4,2,5,3,6, tức $, abcabx$, abx$, bcabx$, bx$, cabx$, x$.

Hơn nữa, LCP của hai hậu tố kề nhau trong mảng hậu tố bằng độ sâu xâu của LCA hai lá đó. Ở ví dụ, mảng LCP là 0,2,0,1,0,0 (LCA của lá 1 và lá 4 là ab, của lá 2 và lá 5 là b), tổng bằng 3, và 21−3=18 đúng bằng số xâu con phân biệt theo công thức của mảng hậu tố. Chiều ngược lại cũng làm được: từ SA + LCP dựng lại cây hậu tố trong O(n) bằng một ngăn xếp (giống dựng cây Cartesian trên mảng LCP). Trong thi đấu, nhiều người dùng SA + LCP thay cho cây hậu tố vì code ngắn và tốn ít bộ nhớ hơn.

Cây hậu tố và Suffix Automaton của xâu đảo ngược

Xây Suffix Automaton cho xâu đảo ngược s―. Cây suffix link của SAM đó chính là cây hậu tố (nén) của s: mỗi đỉnh SAM là một lớp endpos trong s―, tương ứng với một lớp "startpos" trong s, đúng là một đỉnh của cây hậu tố của s. Vì vậy, khi đã có code SAM, có thể lấy cây hậu tố "miễn phí": dựng SAM trên s―, nhãn cạnh từ cha p xuống con v có độ dài len(v)−len(p).

Bảng so sánh nhanh:

Cây hậu tố (Ukkonen) Suffix Array + LCP Suffix Automaton
Dựng O(n) online, code dài, dễ sai O(nlogn), code vừa O(n) online, code ngắn
Bộ nhớ O(nσ), lớn O(n), nhỏ O(nσ)
Mạnh ở Tìm mẫu, đếm lá, LCA trên cây Thứ tự từ điển, truy vấn LCP bằng RMQ Đếm xâu con, LCS, online

Biến thể / Mở rộng

  • Cây hậu tố tổng quát (generalized suffix tree) cho nhiều xâu: dựng trên s1#1s2#2… với mỗi xâu một ký tự phân cách riêng không có trong bảng chữ cái. Mỗi lá được gắn nhãn "thuộc xâu nào" (theo vị trí bắt đầu). Nhãn cạnh lá cắt tại ký tự phân cách đầu tiên.
  • Xâu con chung dài nhất (LCS) của hai xâu a,b: dựng cây tổng quát cho a#b\$, DFS tính cho mỗi đỉnh trong cây con có lá của a không và có lá của b không. Đáp án là đỉnh trong sâu nhất có cả hai loại lá, tổng O(|a|+|b|). Mở rộng cho k xâu: đếm số loại lá khác nhau trong cây con.
  • Xâu con chỉ xuất hiện trong một xâu: trên cây tổng quát, các điểm thuộc cạnh dẫn xuống cây con mà mọi lá đều của xâu i chính là xâu con riêng của xâu i.
  • Xâu con nhỏ thứ k theo từ điển: tính số điểm (xâu con) trong mỗi cây con, đi tham lam từ gốc theo thứ tự ký tự.
  • Online: vì Ukkonen thêm từng ký tự, sau mỗi pha ta có cây ẩn của tiền tố hiện tại; tổng độ dài cạnh (với lá dài tới leafEnd) chính là số xâu con phân biệt của tiền tố đó, không cần $.

Bài tập luyện

  • Tìm Mẫu (findpat) (Rất khó): kiểm tra mỗi mẫu có là xâu con hay không bằng cách đi từ gốc theo mẫu, bài nhập môn để làm quen với nhãn cạnh dạng chỉ số.
  • Đếm Mẫu (cntpat) (Rất khó): số lần xuất hiện mỗi mẫu bằng số lá trong cây con dưới locus, luyện DFS đếm lá và bắt buộc phải có $.
  • Xâu Con Phân Biệt (distsubstr) (Rất khó): đếm xâu con phân biệt bằng tổng độ dài cạnh, đúng như code mẫu ở trên.
  • Xâu Con Lặp Lại (repsubstr) (Rất khó): in xâu con xuất hiện ít nhất hai lần dài nhất, chính là đỉnh trong sâu nhất của cây.
  • Nổi Bật Trong Đàn (standingout) (Chuyên gia): với mỗi xâu đếm các xâu con không xuất hiện ở xâu khác, ứng dụng cây hậu tố tổng quát với lá gắn nhãn theo xâu.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0