SuffixTree Class Reference

Generalised suffix tree alternative to WordTable for indexing non-commutative monomials. More...

#include <SuffixTree.hpp>

Public Member Functions
	SuffixTree ()
	~SuffixTree ()
size_t	monomialCount () const
size_t	insert (const Word &w)
auto	insert (const Word &s, std::vector< Overlap > &newRightOverlaps) -> size_t
const Word	operator[] (int index) const
	Here begin the functions to make the new class swappable with the old WordTable.
void	clear ()
bool	subwords (const Word &word, std::vector< std::pair< int, int > > &output) const
bool	subword (const Word &word, std::pair< int, int > &output) const
bool	superwords (const Word &word, std::vector< std::pair< int, int > > &output) const
auto	isNontrivialSuperword (const Word &word, int index1, int index2) const -> bool
void	leftOverlaps (std::vector< Overlap > &output) const
int	numPatterns () const
auto	splitArc (SuffixTreeNode *f, const Word &prefix) -> SuffixTreeNode *
auto	contractedLocus (SuffixTreeNode *y, const Word &s, bool incrementLeafCount=false) const -> ContractedLocusType
auto	extendedLocus (SuffixTreeNode *x, const Word &beta) const -> ExtendedLocusType
auto	findMatch (SuffixTreeNode *y, const Word &s) const -> ExtendedLocusType
auto	sharedPrefix (const Word s, const Word t) const -> Word
auto	patternLeaves (SuffixTreeNode *v, std::vector< int > &output) const -> void
auto	patternLeavesWorker (SuffixTreeNode *v) const -> std::vector< SuffixTreeNode * >
auto	allLeaves (SuffixTreeNode *v, std::vector< SuffixTreeNode * > &output) const -> void
auto	insert (Label &lab, std::vector< Overlap > &rightOverlaps) -> size_t
auto	insert (std::vector< Label > &labs, std::vector< Overlap > &rightOverlaps) -> size_t
auto	insert (std::vector< Word > &ss, std::vector< Overlap > &rightOverlaps) -> size_t
auto	insertWorker (SuffixTreeNode *v, const Word &s, bool isFullPattern) -> InsertType
auto	insertStepC (SuffixTreeNode *v, SuffixTreeNode *x, const Word &beta, const Word &s, bool isFullPattern) -> InsertType
auto	insertStepD (SuffixTreeNode *y, const Word &s, bool isFullPattern) -> InsertType
auto	subwords (const Word &w, std::vector< std::pair< int, int > > &output, bool onlyFirst) const -> bool
auto	subwordsStepC (SuffixTreeNode *x, const Word &beta, const Word &s) const -> SubwordsType
auto	subwordsStepD (SuffixTreeNode *y, const Word &s) const -> SubwordsType
auto	superword (const Word &w, std::pair< int, int > &output) const -> bool
auto	superwords (const Word &w, std::vector< std::pair< int, int > > &output, bool onlyFirst) const -> bool
auto	leftOverlaps (const Word &w, std::vector< std::pair< int, int > > &output, bool avoidLast=false) const -> void
void	destroyChildren (SuffixTreeNode *node) const

Public Attributes
SuffixTreeNode *	mRoot
std::vector< Label >	mMonomials

Friends
std::ostream &	operator<< (std::ostream &o, const SuffixTree &suffixTree)
void	outputPatterns (std::ostream &o, const SuffixTree &suffixTree)

Detailed Description

Generalised suffix tree alternative to WordTable for indexing non-commutative monomials.

Note

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

Provides the same query surface as WordTable (subword / subwords / leftOverlaps / rightOverlaps, etc.) but backed by a Ukkonen-style suffix tree of SuffixTreeNodes rather than a flat array, giving asymptotically faster subword queries at the cost of a more elaborate insertion path. Currently a drop-in candidate for the WordTable mWordTable slot in NCF4 / NCGroebner — the commented-out SuffixTree mWordTable; in those headers shows the intended swap.

Definition at line 217 of file SuffixTree.hpp.

---

The documentation for this class was generated from the following files:

• Macaulay2/e/NCAlgebras/SuffixTree.hpp
• Macaulay2/e/NCAlgebras/SuffixTree.cpp