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

Kasai's algorithm for constructing longest common prefix array. More...

#include <suffix_array.hpp>

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

Public Member Functions
std::span< const Size >	lcp_array () const
	enhanced_suffix_array (suffix_array< Char, Size, Compare > &&arr)
template<std::ranges::input_range R>
	enhanced_suffix_array (R &&r, const Compare &comp={})
Public Member Functions inherited from step20::suffix_array< Char, Size, Compare >
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.

Additional Inherited Members
Public Types inherited from step20::suffix_array< Char, Size, Compare >
using	value_type = Char
using	size_type = Size

Detailed Description

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

Kasai's algorithm for constructing longest common prefix array.

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

Constructor & Destructor Documentation

enhanced_suffix_array() [1/2]

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

step20::enhanced_suffix_array< Char, Size, Compare >::enhanced_suffix_array ( suffix_array< Char, Size, Compare > &&  arr )

inlineexplicit

enhanced_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::enhanced_suffix_array< Char, Size, Compare >::enhanced_suffix_array ( R &&  r, const Compare &  comp = {}  )

inlineexplicit

Member Function Documentation

lcp_array()

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

std::span< const Size > step20::enhanced_suffix_array< Char, Size, Compare >::lcp_array ( ) const

inline

---

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

• suffix_array.hpp