sdsl/include/sdsl/lcp_construct.hpp File Reference

lcp_construct.hpp contains a space and time efficient construction method for lcp arrays More...

#include "typedefs.hpp"
#include "int_vector.hpp"
#include "rank_support_v.hpp"
#include "util.hpp"
#include "testutils.hpp"
#include "isa_construct.hpp"
#include "bwt_construct.hpp"
#include <iostream>
#include <stdexcept>
#include <list>
#include <algorithm>
#include <fstream>
#include <queue>

Go to the source code of this file.

Classes
class	sdsl::buffered_char_queue
Namespaces
namespace	sdsl
	Namespace for the succinct data structure library.
Typedefs
typedef std::list< int_vector <>::size_type >	sdsl::tLI
typedef std::vector < int_vector<>::size_type >	sdsl::tVI
Functions
bool	sdsl::construct_lcp_kasai (tMSS &file_map, const std::string &dir, const std::string &id)
	5n byte variant of the algorithm of Kasai et al. (CPM 2001, "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications")
bool	sdsl::construct_lcp_semi_extern_PHI (tMSS &file_map, const std::string &dir, const std::string &id)
bool	sdsl::construct_lcp_PHI (tMSS &file_map, const std::string &dir, const std::string &id, bool semi_external=false)
	5n byte variant of the algorithm of Kaerkkaeinen et al. (CPM 2009, "Permuted Longest Common Prefix Array")
template<class size_type_class >
void	sdsl::push_front_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
template<class size_type_class >
void	sdsl::push_back_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
bool	sdsl::construct_lcp_simple_5n (tMSS &file_map, const std::string &dir, const std::string &id)
bool	sdsl::construct_lcp_simple2_9n (tMSS &file_map, const std::string &dir, const std::string &id)
bool	sdsl::construct_lcp_go (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 2n bytes.
bool	sdsl::construct_lcp_goPHI (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 2n bytes.
bool	sdsl::construct_lcp_go2 (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 1 n bytes.
void	sdsl::lcp_info (tMSS &file_map)

---

Detailed Description

lcp_construct.hpp contains a space and time efficient construction method for lcp arrays

Author:

Simon Gog