SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
suffix_array_algorithm.hpp File Reference

suffix_array_algorithm.hpp contains algorithms on CSAs More...

#include <array>
#include <assert.h>
#include <iterator>
#include <stdint.h>
#include <type_traits>
#include <sdsl/config.hpp>
#include <sdsl/csa_wt.hpp>
#include <sdsl/int_vector.hpp>
#include <sdsl/sdsl_concepts.hpp>
#include <sdsl/suffix_array_helper.hpp>
#include <sdsl/wt_pc.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 (t_csa const &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.
 
template<class t_csa >
t_csa::size_type sdsl::forward_search (t_csa const &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.
 
template<class t_csa >
t_csa::size_type sdsl::backward_search (t_csa const &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.
 
template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::backward_search (t_csa const &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.
 
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 (csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > const &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.
 
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 (csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > const &csa_fwd, SDSL_UNUSED csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > const &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.
 
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 csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > const &csa_fwd, csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > const &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.
 
template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::count (t_csa const &csa, t_pat_iter begin, t_pat_iter end, csa_tag)
 Counts the number of occurrences of a pattern in a CSA.
 
template<class t_csx , class t_pat_iter >
t_csx::size_type sdsl::count (t_csx const &csx, t_pat_iter begin, t_pat_iter end)
 
template<class t_csx >
t_csx::size_type sdsl::count (t_csx const &csx, const typename t_csx::string_type &pat)
 Counts the number of occurrences of a pattern in a CSA.
 
template<typename t_csx , typename t_pat_iter >
auto sdsl::lex_interval (t_csx const &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.
 
template<class t_csa , class t_pat_iter , class t_rac = int_vector<64>>
t_rac sdsl::locate (t_csa const &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.
 
template<class t_csx , class t_rac = int_vector<64>>
t_rac sdsl::locate (t_csx const &csx, const typename t_csx::string_type &pat)
 Calculates all occurrences of a pattern pat in a CSA/CST.
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (t_csa const &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].
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (t_csa const &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.
 
template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract (t_csa const &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.
 
template<class t_csa >
t_csa::string_type sdsl::extract (t_csa const &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].
 

Detailed Description

suffix_array_algorithm.hpp contains algorithms on CSAs

Author
Simon Gog

Definition in file suffix_array_algorithm.hpp.