Class SuffixArray

Defined in File SuffixArray.h

Class Documentation

class SuffixArray

the suffix array of a text with its LCP, Llcp and Rlcp arrays and the range minima of LCP

Public Types

using value_type = std::size_t

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using const_reference = const std::size_t&

using reference = const_reference 

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

using iterator = const_iterator 

Public Functions

SuffixArray(void) = default

explicit SuffixArray(std::string_view T): the index of the bytes of T, built by SA-IS and Kasai et al.

SuffixArray(Symbols T, std::size_t K)

the index of an integer text

Pre:: every symbol of T is less than K

std::pair<std::size_t, std::size_t> range(const Symbols &P, long *comparisons = nullptr) const: the range [ first , last ) of SA of the suffixes prefixed by P, by Algorithm 10.1; the comparisons of symbols go to *comparisons, if given

std::pair<std::size_t, std::size_t> range(std::string_view P, long *comparisons = nullptr) const

std::pair<std::size_t, std::size_t> rangeLcp(const Symbols &P, long *comparisons = nullptr) const

range() by the search of Manber and Myers, O( p + log n )

Post:: the range of range( P ) (an audit)

std::pair<std::size_t, std::size_t> rangeLcp(std::string_view P, long *comparisons = nullptr) 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 the order of SA

std::vector<std::size_t> locate(const Symbols &P) const

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, O( 1 )

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

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

the rank of the suffix i in SA

Pre:: i < size()

std::size_t operator[](std::size_t r) const

Pre:: r < size()

inline std::size_t size(void) const

inline const Symbols &text(void) const

inline const std::vector<std::size_t> &lcp(void) const

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const