step20::suffix_tree< Char, Size, Map > Class Template Reference

Ukkonen's online algorithm for constructing suffix tree. More...

#include <suffix_tree.hpp>

Classes
struct	edge_type
struct	slice_type

Public Types
using	value_type = Char
using	size_type = Size

Public Member Functions
const Char *	data () const
Size	size () const
bool	leaf (Size node) const
virtual	~suffix_tree ()=default
void	clear () noexcept
void	push_back (Char ch)
slice_type	label (Size node) const
slice_type	labels (const edge_type &edge) const
std::optional< edge_type >	find (std::ranges::forward_range auto &&str) const
	Find the minimum depth edge which labels start with substring.
generator< edge_type >	depth_first_search (edge_type start) const

Detailed Description

template<class Char, std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>
class step20::suffix_tree< Char, Size, Map >

Ukkonen's online algorithm for constructing suffix tree.

Time complexity O(N*log(K)), space complexity O(N), where: N - text length, K - alphabet size.

Parameters

Char	- type of the characters;
Size	- to specify the maximum number / offset of characters;
Map	- to associate characters with nodes.

Member Typedef Documentation

size_type

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

using step20::suffix_tree< Char, Size, Map >::size_type = Size

value_type

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

using step20::suffix_tree< Char, Size, Map >::value_type = Char

Constructor & Destructor Documentation

~suffix_tree()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

virtual step20::suffix_tree< Char, Size, Map >::~suffix_tree ( )

virtualdefault

Member Function Documentation

clear()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

void step20::suffix_tree< Char, Size, Map >::clear ( )

inlinenoexcept

data()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

const Char * step20::suffix_tree< Char, Size, Map >::data ( ) const

inline

depth_first_search()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

generator< edge_type > step20::suffix_tree< Char, Size, Map >::depth_first_search ( edge_type  start ) const

inline

Space complexity asymptotically close to O(log(N)), O(N) at worst, where: N - text length.

find()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

std::optional< edge_type > step20::suffix_tree< Char, Size, Map >::find ( std::ranges::forward_range auto &&  str ) const

inline

Find the minimum depth edge which labels start with substring.

Time complexity O(M), where: M - substring length.

label()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

slice_type step20::suffix_tree< Char, Size, Map >::label ( Size  node ) const

inline

Returns

characters in node

labels()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

slice_type step20::suffix_tree< Char, Size, Map >::labels ( const edge_type &  edge ) const

inline

Returns

concatenation of characters in [root_node .. edge.child_node]

leaf()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

bool step20::suffix_tree< Char, Size, Map >::leaf ( Size  node ) const

inline

push_back()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

void step20::suffix_tree< Char, Size, Map >::push_back ( Char  ch )

inline

Basic exception guarantee. Content is released if an exception occurs.

size()

template<class Char , std::unsigned_integral Size = std::size_t, class Map = std::unordered_map<Char, Size>>

Size step20::suffix_tree< Char, Size, Map >::size ( ) const

inline

---

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

• suffix_tree.hpp