SuffixTree.hpp File Reference

SuffixTree / SuffixTreeNode — experimental generalised suffix tree for non-commutative leading-word lookup. More...

#include "NCAlgebras/Word.hpp"
#include <iostream>
#include <map>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
class	SuffixTreeNode
	One node of a generalised suffix tree built over the inserted non-commutative monomial patterns. More...
class	SuffixTree
	Generalised suffix tree alternative to WordTable for indexing non-commutative monomials. More...

Typedefs
using	Overlap = std::tuple<int,int,int,bool>
using	Label = std::vector<int>
using	ContractedLocusType
using	ExtendedLocusType
using	InsertType
using	SubwordsType

Functions
void	outputPatterns (std::ostream &o, const SuffixTree &suffixTree)
std::ostream &	operator<< (std::ostream &o, const SuffixTree &suffixTree)
std::ostream &	operator<< (std::ostream &o, const SuffixTreeNode &suffixTreeNode)
void	outputLabel (std::ostream &o, const Label &vec)

Detailed Description

SuffixTree / SuffixTreeNode — experimental generalised suffix tree for non-commutative leading-word lookup.

Note

AI-generated documentation. Verify against the source before relying on it.

Declares the alternative leading-word index for NCGroebner and NCF4. A generalised suffix tree of the basis's leading words gives O(|target|) subword and substring queries regardless of basis size, where the production WordTable pays O(|target| * |basis|). Each SuffixTreeNode stores an arc label (Label = std::vector<int> of variable indices), the cumulative label from the root, child pointers keyed by the first arc symbol (std::map<Label, SuffixTreeNode*>), a suffix link mSuffixLink, and the mIsFullPattern / mPatternLeafCount flags that mark whether a node terminates one of the inserted basis words and how many descendant leaves it covers. The owning SuffixTree class holds the root and the inserted-monomial list, deletes the subtree on clear() / destruction, and offers insert(w) / insert(w, newRightOverlaps), subword / subwords / superwords / isNontrivialSuperword, and leftOverlaps. A rightOverlaps method is commented out with the in-source note "Not sure this is possible in this implementation", which is one of the reasons the production path stays on WordTable.

The Overlap tuple is shared with WordTable so consumers see the same return type whichever index is active. NCGroebner and NCF4 are staged to swap the two indices via toggled //SuffixTree mWordTable; declarations commented out alongside the live WordTable member; in production the WordTable path is used.

See also

Word.hpp

WordTable.hpp

NCGroebner.hpp

NCF4.hpp

Definition in file SuffixTree.hpp.