suffix_tree
クラス · Ukkonen法によるSuffix Tree
template <class T>
struct suffix_tree;
概要
Ukkonen法によるSuffix Tree
文字列または終端記号付きの列から、辺を元列上の半開区間で保持する接尾辞木を構築する。
計算量
- 長さを $n$、遷移の辞書サイズを $\sigma$ として $O(n\log\sigma)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 列sから接尾辞木を構築する (2) 文字列sから接尾辞木を構築する |
$O(n\log\sigma)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
extend |
位置posまでを木へ追加する | 全位置を順に追加したとき償却 $O(\log\sigma)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node |
接尾辞木の1ノード | 遷移の参照・更新は $O(\log\sigma)$ |
メンバ変数
| 名前 | 説明 | 計算量 |
|---|---|---|
s |
構築対象の列 | 参照は $O(1)$ |
nodes |
全ノード | 参照は $O(1)$ |
root |
根ノードID | 参照は $O(1)$ |
active_node |
Ukkonen法のactive node | 参照は $O(1)$ |
active_edge |
Ukkonen法のactive edge開始位置 | 参照は $O(1)$ |
active_len |
Ukkonen法のactive edge内長 | 参照は $O(1)$ |
remainder |
未処理suffix数 | 参照は $O(1)$ |
メンバの詳細
(constructor)
// (1)
suffix_tree(const std::vector<T> &_s);
// (2)
suffix_tree(const std::string &_s);
(1) 列sから接尾辞木を構築する
- 計算量: $O(n\log\sigma)$
(2) 文字列sから接尾辞木を構築する
- 計算量: $O(n\log\sigma)$
node
struct node;
接尾辞木の1ノード
- 計算量: 遷移の参照・更新は $O(\log\sigma)$
| メンバ | 説明 |
|---|---|
end |
親辺が表す元列上の半開区間[start,end) |
link |
suffix link先のノードID |
next |
先頭要素ごとの子遷移 |
node |
親辺の区間からノードを構築する |
len |
親辺の長さを返す |