SDSL 3.0.1
Succinct Data Structure Library
suffix_array_algorithm.hpp File Reference

suffix_array_algorithm.hpp contains algorithms on CSAs More...

#include <iterator>
#include <sdsl/csa_wt.hpp>
#include <sdsl/suffix_array_helper.hpp>

Go to the source code of this file.

Namespaces

namespace  sdsl
 Namespace for the succinct data structure library.
 

Functions

template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::forward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, t_pat_iter begin, t_pat_iter end, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Forward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa >
t_csa::size_type sdsl::forward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Forward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa >
t_csa::size_type sdsl::backward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Backward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::backward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, t_pat_iter begin, t_pat_iter end, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Backward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type sdsl::bidirectional_search (const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, typename csa_wt<>::char_type c, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search for a character c on an interval $[l_fwd..r_fwd]$ of the suffix array. More...
 
template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt ::size_type sdsl::bidirectional_search_backward (const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_bwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, t_pat_iter begin, t_pat_iter end, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search in backward direction. More...
 
template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type sdsl::bidirectional_search_forward (SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_bwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, t_pat_iter begin, t_pat_iter end, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search in forward direction. More...
 
template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::count (const t_csa &csa, t_pat_iter begin, t_pat_iter end, csa_tag)
 Counts the number of occurrences of a pattern in a CSA. More...
 
template<class t_csx , class t_pat_iter >
t_csx::size_type sdsl::count (const t_csx &csx, t_pat_iter begin, t_pat_iter end)
 
template<class t_csx >
t_csx::size_type sdsl::count (const t_csx &csx, const typename t_csx::string_type &pat)
 Counts the number of occurrences of a pattern in a CSA. More...
 
template<typename t_csx , typename t_pat_iter >
auto sdsl::lex_interval (const t_csx &csx, t_pat_iter begin, t_pat_iter end) -> std::array< typename t_csx::size_type, 2 >
 Returns the lexicographic interval of a pattern in the SA. More...
 
template<class t_csa , class t_pat_iter , class t_rac = int_vector<64>>
t_rac sdsl::locate (const t_csa &csa, t_pat_iter begin, t_pat_iter end, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Calculates all occurrences of a pattern pat in a CSA. More...
 
template<class t_csx , class t_rac = int_vector<64>>
t_rac sdsl::locate (const t_csx &csx, const typename t_csx::string_type &pat)
 Calculates all occurrences of a pattern pat in a CSA/CST. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Writes the substring T[begin..end] of the original text T to text[0..end-begin+1]. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, lf_tag)
 Specialization of extract for LF-function based CSAs. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, psi_tag)
 Specialization of extract for $\Psi$-function based CSAs. More...
 
template<class t_csa >
t_csa::string_type sdsl::extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Reconstructs the substring T[begin..end] of the original text T to text[0..end-begin+1]. More...
 

Detailed Description

suffix_array_algorithm.hpp contains algorithms on CSAs

Author
Simon Gog

Definition in file suffix_array_algorithm.hpp.