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.
Cây hậu tố (suffix tree) của xâu độ dài là cây chứa mọi hậu tố của , trong đó mỗi xâu con của ứ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 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 đỉnh, còn cây hậu tố nén chỉ có đỉnh, và thuật toán Ukkonen dựng nó online (thêm từng ký tự) trong thay vì .
Ý 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ố 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 đỉ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 lá, nên số đỉnh trong và tổng số đỉnh .
- Nhãn cạnh không lưu thành xâu (tổng độ dài vẫn có thể là ) mà lưu bằng hai chỉ số trỏ vào , nên bộ nhớ là .
Ví dụ với : 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 : 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 là xâu con của khi và chỉ khi 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 gọi là locus của . 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 : đi từ gốc theo các ký tự của , mất .
- Số lần xuất hiện của = số lá trong cây con dưới locus của (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ý từ trái sang phải. Sau pha (đã đọc ), ta có cây ẩn của . Thêm ký tự nghĩa là kéo dài mọi hậu tố thêm . Làm thô thì mỗi pha tốn hậu tố, tổng (thậm chí nếu đi lại từ gốc). Ba mẹo biến nó thành :
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 . 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 . Đâ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ố :
- Nếu sau locus của chưa có ký tự : 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ự : đã nằm trong cây, và mọi hậu tố ngắn hơn của 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ố (với là ký tự đầu), hậu tố kế tiếp cần chèn là . Để nhảy nhanh từ locus của sang locus của :
- Mỗi đỉnh trong ứng với xâu có suffix link trỏ tới đỉnh ứng với . Nếu
activeNodekhác gốc, chỉ cầnactiveNode = link[activeNode], giữ nguyên cạnh và độ dài. - Nếu
activeNodelà gốc thì bỏ ký tự đầu:activeLength--,activeEdgedời sang phải một vị trí. - Khi
activeLengthdà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ợ:
remainder = 3, locus là (gốc,a, 2), tức sauabtrên cạnhabcabx. Ký tự kế trên cạnh làckhácx: tách cạnh tạiab, tạo đỉnh trong =ab, gắn láxvào .remainder = 2. Đang ở gốc nênactiveLength = 1,activeEdgechuyển sangb.- Locus (gốc,
b, 1), saublàckhácx: tách cạnh tạo đỉnh =b, gắn láx. Gán suffix link (vìabbỏ ký tự đầu làb).remainder = 1,activeLength = 0. - Locus là gốc, gốc chưa có cạnh
x: tạo láx. Gán link 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,ab2,cabx$5,x$2,b1,cabx$5,x$2,cabx$5,x$2, tổng . Mỗi cạnh trong 7 cạnh lá kết thúc bằng$nên trừ 7, còn . Đối chiếu: có 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 . 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ạnhbđến , cạnhcabx$khớpca: 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 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".
#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";
}
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 |
18ab |
cabababc |
25abab |
abaa |
8a |
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 trong khoảng giây.
Để tìm mẫu , đi từ gốc: tại đỉnh chọn con nxt[v][p[k]], so lần lượt các ký tự trên nhãn cạnh với ; lệch một ký tự là không có, đi hết 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 với cài đặt mảng con cỡ (khởi tạo mảng tốn mỗi đỉnh), hoặc với
map. Phần thuật toán Ukkonen chỉ tốn bước:- Mỗi lần áp luật 2 giảm
remainderđi 1, màremainderchỉ tăng đúng 1 mỗi pha, nên tổng số lần chèn tường minh . 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,
activeLengthgiảm ít nhất 1.activeLengthchỉ 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à . Đi theo suffix link không làm tăngactiveLength.
- Mỗi lần áp luật 2 giảm
- Bộ nhớ : tối đa đỉnh (với tính cả
$), mỗi đỉnh lưu 3 số nguyên và mảng con. Với và là khoảng 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, . Tìm mẫu: .
⚠️ 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ớiaa, cây ẩn chỉ có một cạnhaa, 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ônextend('$')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 . - Lưu nhãn cạnh bằng
string. Tổng độ dài các nhãn có thể là (cạnh lá từ gốc dài gần ), cùng với việc cập nhật lá mỗi pha thì thành thời gian và bộ nhớ. Luôn lưu cặp chỉ số và dùng một biếnleafEndchung cho mọi lá. - Thiếu bước skip/count (
if (actLen >= edgeLen(nx))). KhiactiveLengthdài hơn cạnh, phép sotext[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ảmremainder. Đặt lệnh này trướcremainder--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,activeLengthcủ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
intcho số xâu con phân biệt. Đáp số tới với : dùnglong long. - Mảng con cỡ khi lớn. Với thì số
intlà khoảng 216 MB, vượt giới hạn. Đổi sangmap, 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à , tức $, abcabx$, abx$, bcabx$, bx$, cabx$, x$.
Hơn nữa, 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à (LCA của lá 1 và lá 4 là ab, của lá 2 và lá 5 là b), tổng bằng , và đú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 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 . Cây suffix link của SAM đó chính là cây hậu tố (nén) của : mỗi đỉnh SAM là một lớp endpos trong , tương ứng với một lớp "startpos" trong , đúng là một đỉnh của cây hậu tố của . Vì vậy, khi đã có code SAM, có thể lấy cây hậu tố "miễn phí": dựng SAM trên , nhãn cạnh từ cha xuống con có độ dài .
Bảng so sánh nhanh:
| Cây hậu tố (Ukkonen) | Suffix Array + LCP | Suffix Automaton | |
|---|---|---|---|
| Dựng | online, code dài, dễ sai | , code vừa | online, code ngắn |
| Bộ nhớ | , lớn | , nhỏ | |
| 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 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 : dựng cây tổng quát cho $, DFS tính cho mỗi đỉnh trong cây con có lá của không và có lá của không. Đáp án là đỉnh trong sâu nhất có cả hai loại lá, tổng . Mở rộng cho 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 chính là xâu con riêng của xâu .
- Xâu con nhỏ thứ 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.
Bình luận