step20::suffix_array< Char, Size, Compare > Class Template Reference

Manber's algorithm for constructing sorted array of non-empty suffixes. More...

#include <suffix_array.hpp>

Inheritance diagram for step20::suffix_array< Char, Size, Compare >:

Public Types
using	value_type = Char
using	size_type = Size

Public Member Functions
const Char *	data () const
Size	size () const
Size	operator[] (Size n) const
	suffix position
const Compare &	comp () const
virtual	~suffix_array ()=default
	suffix_array (std::basic_string< Char > str, const Compare &comp={})
template<std::ranges::input_range R>
	suffix_array (R &&r, const Compare &comp={})
std::span< const Size >	find (std::ranges::input_range auto &&str) const
	Find positions of suffixes starting with substring.

Detailed Description

template<class Char, std::unsigned_integral Size = std::size_t, class Compare = std::less<>>
class step20::suffix_array< Char, Size, Compare >

Manber's algorithm for constructing sorted array of non-empty suffixes.

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

Parameters

Char	- type of the characters;
Size	- to specify the maximum number / offset of characters;
Compare	- to determine the order of characters.

Member Typedef Documentation

size_type

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

using step20::suffix_array< Char, Size, Compare >::size_type = Size

value_type

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

using step20::suffix_array< Char, Size, Compare >::value_type = Char

Constructor & Destructor Documentation

~suffix_array()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

virtual step20::suffix_array< Char, Size, Compare >::~suffix_array ( )

virtualdefault

suffix_array() [1/2]

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

step20::suffix_array< Char, Size, Compare >::suffix_array ( std::basic_string< Char >  str, const Compare &  comp = {}  )

inlineexplicit

suffix_array() [2/2]

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

template<std::ranges::input_range R>

step20::suffix_array< Char, Size, Compare >::suffix_array ( R &&  r, const Compare &  comp = {}  )

inlineexplicit

Member Function Documentation

comp()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

const Compare & step20::suffix_array< Char, Size, Compare >::comp ( ) const

inline

data()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

const Char * step20::suffix_array< Char, Size, Compare >::data ( ) const

inline

find()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

std::span< const Size > step20::suffix_array< Char, Size, Compare >::find ( std::ranges::input_range auto &&  str ) const

inline

Find positions of suffixes starting with substring.

Time complexity O(M*log(N)), where: M - substring length, N - text length.

operator[]()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

Size step20::suffix_array< Char, Size, Compare >::operator[] ( Size  n ) const

inline

suffix position

size()

template<class Char , std::unsigned_integral Size = std::size_t, class Compare = std::less<>>

Size step20::suffix_array< Char, Size, Compare >::size ( ) const

inline

---

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

• suffix_array.hpp