Suffix_Structures.H File Reference

Suffix structures: suffix array/LCP, suffix tree, suffix automaton. More...

#include <algorithm>
#include <limits>
#include <string>
#include <string_view>
#include <utility>
#include <array>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_sort_utils.H>

Include dependency graph for Suffix_Structures.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Naive_Suffix_Tree
	Naive compressed suffix tree (didactic implementation). More...
struct	Aleph::Naive_Suffix_Tree::Node
	One tree node. More...
class	Aleph::Suffix_Automaton
	Suffix automaton (SAM) over byte alphabet. More...
struct	Aleph::Suffix_Automaton::State
	One automaton state. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::suffix_structures_detail

Functions
Array< size_t >	Aleph::suffix_structures_detail::all_positions (const size_t n)
	Generate an array of all positions from 0 to n.
void	Aleph::suffix_structures_detail::sort_matches (Array< size_t > &a)
	Sort matches in place using introsort.
Array< size_t >	Aleph::suffix_array (const std::string_view text)
	Build suffix array with doubling algorithm.
Array< size_t >	Aleph::lcp_array_kasai (const std::string_view text, const Array< size_t > &sa)
	Compute LCP array from text and suffix array using Kasai.
std::string	Aleph::longest_common_substring_sam (const std::string_view a, const std::string_view b)
	Convenience function: LCS via suffix automaton.

Detailed Description

Suffix structures: suffix array/LCP, suffix tree, suffix automaton.

Includes:

• Suffix array via doubling O(n log n)
• LCP array via Kasai O(n)
• Didactic naive compressed suffix tree O(n^2)
• Suffix automaton O(n)

Definition in file Suffix_Structures.H.