cst_sct3 ()=default
Default constructor.
cst_sct3 (cache_config &cache, bool build_only_bps=false)
Construct CST from cache config.
cst_sct3 (const cst_sct3 &cst)
Copy constructor.
cst_sct3 (cst_sct3 &&cst)
Move constructor.
size_type size () const
Number of leaves of the suffix tree.
bool empty () const
Returns if the data structure is empty.
const_iterator begin () const
Returns a const_iterator to the first element of a depth first traversal of the tree.
const_iterator begin (const node_type &v) const
Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v.
const_iterator end () const
Returns a const_iterator to the element after the last element of a depth first traversal of the tree.
const_iterator end (const node_type &v) const
Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted at node v.
const_bottom_up_iterator begin_bottom_up () const
Returns an iterator to the first element of a bottom-up traversal of the tree.
const_bottom_up_iterator end_bottom_up () const
Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
cst_sct3 & operator= (const cst_sct3 &cst)
Assignment Operator.
cst_sct3 & operator= (cst_sct3 &&cst)
Assignment Move Operator.
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
void load (std::istream &in)
Load from a stream.
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
Serialise (save) via cereal.
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
Serialise (load) via cereal.
bool operator== (cst_sct3 const &other) const noexcept
Equality operator.
bool operator!= (cst_sct3 const &other) const noexcept
Inequality operator.
node_type root () const
Return the root of the suffix tree.
bool is_leaf (const node_type &v) const
Decide if a node is a leaf.
node_type select_leaf (size_type i) const
Return the i-th leaf (1-based from left to right).
size_type size (const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
node_type leftmost_leaf (const node_type &v) const
Calculates the leftmost leaf in the subtree rooted at node v.
node_type rightmost_leaf (const node_type &v) const
Calculates the rightmost leaf in the subtree rooted at node v.
size_type lb (const node_type &v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
size_type rb (const node_type &v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
node_type parent (const node_type &v) const
Calculate the parent node of a node v.
cst_node_child_proxy < cst_sct3 > children (const node_type &v) const
Return a proxy object which allows iterating over the children of a node.
node_type sibling (const node_type &v) const
Returns the next sibling of node v.
node_type select_child (const node_type &v, size_type i) const
Get the i-th child of a node v.
size_type degree (const node_type &v) const
Get the number of children of a node v.
node_type child (const node_type &v, const char_type c, size_type &char_pos) const
Get the child w of node v which edge label (v,w) starts with character c.
node_type child (const node_type &v, const char_type c) const
Get the child w of node v which edge label (v,w) starts with character c.
char_type edge (const node_type &v, size_type d) const
Returns the d-th character (1-based indexing) of the edge-label pointing to v.
node_type lca (node_type v, node_type w) const
Calculate the LCA of two nodes v
and w
size_type depth (const node_type &v) const
Returns the string depth of node v.
size_type node_depth (node_type v) const
Returns the node depth of node v.
node_type sl (const node_type &v) const
Compute the suffix link of node v.
node_type wl (const node_type &v, const char_type c) const
Compute the Weiner link of node v and character c.
size_type sn (const node_type &v) const
Computes the suffix number of a leaf node v.
size_type id (const node_type &v) const
Computes a unique identification number for a node of the suffx tree in the range [0..nodes() -1].
node_type inv_id (size_type id )
Computes the node for such that id(v)=id.
size_type nodes () const
Get the number of nodes of the suffix tree.
node_type node (size_type lb , size_type rb ) const
Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
size_type tlcp_idx (size_type i) const
Maps an index i to the position in TLCP where LCP[i] can be found.
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
class sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >
A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog.
Template Parameters
t_csa Type of a CSA (member of this type is accessible via member csa
, default class is sdsl::csa_sada ).
t_lcp Type of a LCP structure (member is accessible via member lcp
, default class is sdsl::lcp_support_sada ),
t_bp_support Type of a BPS structure (member accessible via member bp_support
, default class is sdsl::bp_support_sada ),
t_rank Type of rank structure which supports the bitvector which indicates the leftmost child of the nodes.
It also contains a sdsl::bit_vector which represents the BP sequence of the Super-Cartesian tree of the LCP array. This bitvector can be accessed via the member bp
. Another sdsl::bit_vector stores information, if a node is the leftmost child of another node. This bitvector can be access via the member first_child_bv and takes n bits.
A node of the csa_sct is represented by an sdsl::bp_interval . The size of the sdsl::cst_sct3 is smaller than the size of a sdsl::cst_sada since the tree topology needs only bits in contrast to the bits in sdsl::cst_sada .
Reference Enno Ohlebusch, Johannes Fischer, Simon Gog: CST++. SPIRE 2010: 322-333
Applications of the CST The compressed suffix tree could be used for string matching and many other application in sequence analysis. 17 applications are in the book "Algorithms on Strings, Trees, and Sequences" of Dan Gusfield.
Definition at line 89 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
Returns a const_iterator to the first element of a depth first traversal of the tree.
Required for the STL Container Concept.
See also end
Definition at line 413 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
Get the child w of node v which edge label (v,w) starts with character c.
Parameters
v A valid tree node of the cst.
c First character on the edge label.
char_pos Reference which will hold the position (0-based) of the matching char c in the sorted text/suffix array.
Returns The child node w which edge label (v,w) starts with c or root() if it does not exist.
Time complexity
Definition at line 787 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
bool sdsl::cst_sct3 < t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::empty
(
)
const
inline
Returns if the data structure is empty.
Required for the Container Concept of the STL.
See also size
Definition at line 407 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
Returns a const_iterator to the element after the last element of a depth first traversal of the tree.
Required for the STL Container Concept.
See also begin .
Definition at line 431 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
Returns the largest size that cst_sct3 can ever have.
Required for the Container Concept of the STL.
See also size
Definition at line 401 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
cst_sct3 & sdsl::cst_sct3 < t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::operator=
(
cst_sct3 < t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > &&
cst )
inline
Assignment Move Operator.
Required for the Assignable Concept of the STL.
Definition at line 469 of file cst_sct3.hpp .
template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
Number of leaves of the suffix tree.
Required for the Container Concept of the STL.
See also max_size , empty
Definition at line 395 of file cst_sct3.hpp .