suffix.hpp File Reference

Suffix array algorithms. More...

Go to the source code of this file.

Namespaces
	shore
	SHORE core API.

Constant Groups
	shore
	SHORE core API.

Functions
template<typename Iter , typename Oter >
void	shore::count_elements (Iter ibeg, Iter iend, Oter obeg, Oter oend, bool initialize_counts=true, int shift=0)
	Count elements in a range. More...
template<typename Iter >
void	shore::counts_to_intervals (Iter beg, Iter end)
template<typename Iter , typename Oter >
void	shore::suffix_array (Iter ibeg, Iter iend, Oter obeg, bool initialize_sa=true, typename std::iterator_traits< Iter >::value_type imax=std::numeric_limits< typename std::iterator_traits< Iter >::value_type >::max())
	Construct suffix array; values in input range must not be negative. More...
template<typename Ater , typename Oter >
void	shore::suffix_ranks (Ater abeg, Ater aend, Oter rbeg)
template<typename Ster , typename Ater >
std::pair< size_t, size_t >	shore::suffix_lcpmax (Ster sbeg, Ster send, Ater abeg)
	Get the value and position of the maximal lcp for a suffix array.
template<typename Ster , typename Ater , typename Oter >
void	shore::suffix_lcp (Ster sbeg, Ster send, Ater abeg, Oter obeg)
	Construct the lcp array for a suffix array.
template<typename Ster , typename Ater , typename Qter >
std::pair< Ater, Ater >	shore::suffix_query (Ster sbeg, Ster send, Ater abeg, Ater aend, Qter qbeg, Qter qend)
	Binary search on a suffix array.
template<typename Ster , typename Ater , typename Qter >
suffix_query_result< Ater, Qter >	shore::suffix_query_prefix (Ster sbeg, Ster send, Ater abeg, Ater aend, Qter qbeg, Qter qend)
	Binary search on a suffix array.
template<typename Ster , typename Ater , typename Query >
std::pair< Ater, Ater >	shore::suffix_query_incremental (Ster sbeg, Ster send, Ater abeg, Ater aend, const Query q, const size_t ofs)
	Binary search on a suffix array. More...
template<typename Ster , typename Ater , typename Qter >
std::pair< Ater, Ater >	shore::suffix_query (Ster sbeg, Ster send, Ater abeg, Qter qbeg, Qter qend)
	Binary search on a suffix array.
template<typename Ster , typename Ater , typename Qter >
suffix_query_result< Ater, Qter >	shore::suffix_query_prefix (Ster sbeg, Ster send, Ater abeg, Qter qbeg, Qter qend)
	Binary search on a suffix array.
template<typename Ster , typename Ater >
std::ostream &	shore::suffix_dump (std::ostream &os, Ster sbeg, Ster send, Ater abeg)
template<typename Ster , typename Ater >
bool	shore::suffix_test (Ster sbeg, Ster send, Ater abeg)
	Test correctness of a suffix array (slow)

Detailed Description

Suffix array algorithms.

Author

Felix Ott