25 unsigned SuffixesToAdd = 0;
30 for (
unsigned PfxEndIdx = 0, End =
Str.
size(); PfxEndIdx < End; PfxEndIdx++) {
32 LeafEndIdx = PfxEndIdx;
33 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
37 assert(Root &&
"Root node can't be nullptr!");
42 unsigned StartIdx,
unsigned Edge) {
44 assert(StartIdx <= LeafEndIdx &&
"String can't start after it ends!");
55 unsigned EndIdx,
unsigned Edge) {
57 assert(StartIdx <= EndIdx &&
"String can't start after it ends!");
59 "Non-root internal nodes must have parents!");
61 unsigned *
E =
new (InternalEndIdxAllocator)
unsigned(EndIdx);
70 void SuffixTree::setSuffixIndices() {
73 std::vector<std::pair<SuffixTreeNode *, unsigned>> ToVisit;
79 unsigned CurrNodeLen = 0;
80 ToVisit.push_back({CurrNode, CurrNodeLen});
81 while (!ToVisit.empty()) {
82 std::tie(CurrNode, CurrNodeLen) = ToVisit.back();
85 for (
auto &ChildPair : CurrNode->
Children) {
86 assert(ChildPair.second &&
"Node had a null child!");
88 {ChildPair.second, CurrNodeLen + ChildPair.second->size()});
97 unsigned SuffixTree::extend(
unsigned EndIdx,
unsigned SuffixesToAdd) {
100 while (SuffixesToAdd > 0) {
103 if (Active.Len == 0) {
108 assert(Active.Idx <= EndIdx &&
"Start index can't be after end index!");
111 unsigned FirstChar =
Str[Active.Idx];
114 if (Active.Node->Children.count(FirstChar) == 0) {
116 insertLeaf(*Active.Node, EndIdx, FirstChar);
121 NeedsLink->
Link = Active.Node;
129 unsigned SubstringLen = NextNode->
size();
133 if (Active.Len >= SubstringLen) {
136 Active.Idx += SubstringLen;
137 Active.Len -= SubstringLen;
138 Active.Node = NextNode;
144 unsigned LastChar =
Str[EndIdx];
147 if (
Str[NextNode->
StartIdx + Active.Len] == LastChar) {
151 if (NeedsLink && !Active.Node->isRoot()) {
152 NeedsLink->
Link = Active.Node;
175 insertInternalNode(Active.Node, NextNode->
StartIdx,
176 NextNode->
StartIdx + Active.Len - 1, FirstChar);
180 insertLeaf(*SplitNode, EndIdx, LastChar);
189 NeedsLink->
Link = SplitNode;
191 NeedsLink = SplitNode;
198 if (Active.Node->isRoot()) {
199 if (Active.Len > 0) {
201 Active.Idx = EndIdx - SuffixesToAdd + 1;
205 Active.Node = Active.Node->Link;
209 return SuffixesToAdd;