3#ifndef STEP20_SUFFIX_TREE_HPP
4#define STEP20_SUFFIX_TREE_HPP
10#include <unordered_map>
22 std::unsigned_integral Size = std::size_t,
23 class Map = std::unordered_map<Char, Size>>
28 const Char*
data()
const {
return str_.data(); }
29 Size
size()
const {
return str_.size(); }
30 bool leaf(Size node)
const {
return node >= nodes_.size(); }
46 nodes_.emplace_back();
47 auto tie = [
this, src = nodes_.size()](Size dest)
mutable {
48 if (!
leaf(src) && src != dest)
49 nodes_[src++].link = dest;
51 while (pos_ <
size()) {
52 if (Size& node = nodes_[node_].children[str_[pos_]]) {
57 tie(nodes_.size() - 1);
63 node_ ? node_ = nodes_[node_].link : ++pos_;
98 std::optional<edge_type>
find(std::ranges::forward_range
auto&& str)
const
102 auto first = std::ranges::begin(str);
103 auto last = std::ranges::end(str);
105 auto lbl =
label(edge.child_node);
106 edge.labels_len += lbl.length();
107 auto diff = std::mismatch(
108 first, last,
data() + lbl.first,
data() + lbl.last, eq_);
109 if (diff.first == last)
111 if (diff.second !=
data() + lbl.last ||
leaf(edge.child_node))
113 auto it = nodes_[edge.child_node].children.find(*diff.first);
114 if (it == nodes_[edge.child_node].children.end())
117 edge.parent_node = std::exchange(edge.child_node, it->second);
125 for (
auto stack = std::stack<edge_type>{{start}}; !stack.empty();) {
126 auto edge = stack.top();
129 if (!
leaf(edge.child_node))
131 try_reverse(nodes_[edge.child_node].children) |
132 std::views::transform([&](
auto&& item) {
136 edge.labels_len + label(item.second).length()};
138 emplace_iterator(stack));
149 inline static auto eq_ = key_equivalence_fn<Map>();
150 std::basic_string<Char> str_;
151 std::vector<node_type> nodes_;
152 Size pos_{}, node_{};
156 Size len = label(node).length();
157 if (size() <= pos_ + len)
164 bool split(Size& node)
166 auto lbl = label(node);
167 Size cut = lbl.first + (size() - pos_) - 1;
168 Size back = size() - 1;
169 if (eq_(str_[cut], str_[back]))
171 Size old = std::exchange(node, (Size)nodes_.size());
172 nodes_.push_back({{{str_[cut], leaf(old) ? flip(cut) : old},
173 {str_[back], flip(back)}},
176 nodes_[old].label = {cut, lbl.last};
Ukkonen's online algorithm for constructing suffix tree.
Definition suffix_tree.hpp:24
virtual ~suffix_tree()=default
void push_back(Char ch)
Definition suffix_tree.hpp:42
Char value_type
Definition suffix_tree.hpp:26
slice_type labels(const edge_type &edge) const
Definition suffix_tree.hpp:89
std::optional< edge_type > find(std::ranges::forward_range auto &&str) const
Find the minimum depth edge which labels start with substring.
Definition suffix_tree.hpp:98
Size size_type
Definition suffix_tree.hpp:27
const Char * data() const
Definition suffix_tree.hpp:28
bool leaf(Size node) const
Definition suffix_tree.hpp:30
generator< edge_type > depth_first_search(edge_type start) const
Definition suffix_tree.hpp:123
slice_type label(Size node) const
Definition suffix_tree.hpp:83
void clear() noexcept
Definition suffix_tree.hpp:33
Size size() const
Definition suffix_tree.hpp:29
Definition edit_distance.hpp:11
Definition generator.hpp:19
Definition suffix_tree.hpp:76
Size labels_len
number of characters in [root_node .. child_node]
Definition suffix_tree.hpp:79
Size parent_node
Definition suffix_tree.hpp:77
Size child_node
Definition suffix_tree.hpp:78
Definition suffix_tree.hpp:71
Size first
Definition suffix_tree.hpp:72
Size length() const
Definition suffix_tree.hpp:73
Size last
half-open character range
Definition suffix_tree.hpp:72