Class SuffixTree

Defined in File SuffixTree.h

Nested Relationships

Nested Types

Struct SuffixTree::Node

Class Documentation

class SuffixTree

the suffix tree of T$, its nodes in a vector, the root at 0

Public Types

enum class Build

the construction

Values:

enumerator naive

enumerator mcCreight

enumerator suffixArray

using value_type = Node 

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using const_reference = const Node&

using reference = const_reference 

using const_iterator = std::vector<Node>::const_iterator

using iterator = const_iterator 

Public Functions

SuffixTree(void) = default

explicit SuffixTree(std::string_view T, Build b = Build::mcCreight): the suffix tree of the bytes of T

SuffixTree(const Symbols &T, std::size_t K, Build b = Build::mcCreight)

the suffix tree of an integer text

Pre:: every symbol of T is less than K

std::size_t textSize(void) const: the length n of T, without the terminator

inline std::size_t root(void) const

const Node &node(std::size_t u) const

Pre:: u < size()

std::size_t leaf(std::size_t i) const

the leaf of the suffix i, the terminator being the suffix n

Pre:: i <= textSize()

std::size_t symbol(std::size_t i) const

the symbol at the place i of T$ as stored: the symbols of T plus 1, and 0 for the terminator at n

Pre:: i <= textSize()

std::size_t locus(std::string_view P) const: the extended locus of P, or npos if P does not occur

std::size_t locus(const Symbols &P) const

std::size_t count(std::string_view P) const: the number of occurrences of P

std::vector<std::size_t> locate(std::string_view P) const: the places of the occurrences of P, in lexicographic order of their suffixes; the empty pattern at the n places of the suffixes

std::size_t lca(std::size_t u, std::size_t v) const

the lowest common ancestor of u and v, O( 1 )

Pre:: u < size() and v < size()

std::size_t lce(std::size_t i, std::size_t j) const

the length of the longest common prefix of the suffixes i and j of T

Pre:: i <= textSize() and j <= textSize()

std::pair<std::vector<std::size_t>, std::vector<std::size_t>> toSuffixArray(void) const: SA and LCP of T, by a visit in order (Fact 10.5)

std::vector<std::size_t> preorder(void) const: the nodes in preorder, the children by increasing first symbol

inline std::size_t size(void) const: the number of nodes

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

Public Static Attributes

static constexpr std::size_t npos = std::numeric_limits<std::size_t>::max(): no node, no suffix

struct Node

a node u; the edge into it is labelled by the symbols of T from pos + depth of the parent to pos + depth (the terminator at n)

Public Members

std::size_t pos = 0: the start of an occurrence of s[ u ]

std::size_t depth = 0: the string depth | s[ u ] |

std::size_t parent = npos : npos at the root

std::size_t suffix = npos : the suffix of a leaf, npos inside

std::size_t leaves = 0: the leaves below, occ[ u ]

std::map<std::size_t, std::size_t> child: by first symbol