This namespace contains helper functions for the Ukkonen class.

Functions
void	add_word (Ukkonen &u, char const *w)
	Add a word to the suffix tree.

template<typename Iterator>
void	add_word (Ukkonen &u, Iterator first, Iterator last)
	Add a word to the suffix tree.

template<typename Word>
void	add_word (Ukkonen &u, Word const &w)
	Add a word to the suffix tree.

void	add_word (Ukkonen &u, word_type const &w)
	Add a word to the suffix tree.

void	add_word_no_checks (Ukkonen &u, char const *w)
	Add a word to the suffix tree.

template<typename Iterator>
void	add_word_no_checks (Ukkonen &u, Iterator first, Iterator last)
	Add a word to the suffix tree.

template<typename Word>
void	add_word_no_checks (Ukkonen &u, Word const &w)
	Add a word to the suffix tree.

void	add_word_no_checks (Ukkonen &u, word_type const &w)
	Add a word to the suffix tree.

template<typename Iterator1, typename Iterator2>
void	add_words (Ukkonen &u, Iterator1 first, Iterator2 last)
	Add all words in a range to a Ukkonen object.

void	add_words (Ukkonen &u, std::vector< word_type > const &words)
	Add all words in a range to a Ukkonen object.

template<typename Iterator1, typename Iterator2>
void	add_words_no_checks (Ukkonen &u, Iterator1 first, Iterator2 last)
	Add all words in a range to a Ukkonen object.

void	add_words_no_checks (Ukkonen &u, std::vector< word_type > const &words)
	Add all words in a std::vector to a Ukkonen object.

template<typename T>
auto	dfs (Ukkonen const &u, T &helper)
	Perform a depth first search in a suffix tree.

Dot	dot (Ukkonen const &u)
	Returns a Dot object representing a suffix tree.

bool	is_piece (Ukkonen const &u, char const *w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

template<typename Iterator>
bool	is_piece (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

template<typename Word>
bool	is_piece (Ukkonen const &u, Word const &w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

bool	is_piece (Ukkonen const &u, word_type const &w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

bool	is_piece_no_checks (Ukkonen const &u, char const *w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

template<typename Iterator>
bool	is_piece_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

template<typename Word>
bool	is_piece_no_checks (Ukkonen const &u, Word const &w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

bool	is_piece_no_checks (Ukkonen const &u, word_type const &w)
	Check if a word is a piece (occurs in two distinct places in the words of the suffix tree).

bool	is_subword (Ukkonen const &u, char const *w)
	Check if a word is a subword of any word in a suffix tree.

template<typename Iterator>
bool	is_subword (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a subword of any word in a suffix tree.

template<typename Word>
bool	is_subword (Ukkonen const &u, Word const &w)
	Check if a word is a subword of any word in a suffix tree.

bool	is_subword (Ukkonen const &u, word_type const &w)
	Check if a word is a subword of any word in a suffix tree.

bool	is_subword_no_checks (Ukkonen const &u, char const *w)
	Check if a word is a subword of any word in a suffix tree.

template<typename Iterator>
bool	is_subword_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a subword of any word in a suffix tree.

template<typename Word>
bool	is_subword_no_checks (Ukkonen const &u, Word const &w)
	Check if a word is a subword of any word in a suffix tree.

bool	is_subword_no_checks (Ukkonen const &u, word_type const &w)
	Check if a word is a subword of any word in a suffix tree.

bool	is_suffix (Ukkonen const &u, char const *w)
	Check if a word is a suffix of any word in a suffix tree.

template<typename Iterator>
bool	is_suffix (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a suffix of any word in a suffix tree.

template<typename Word>
bool	is_suffix (Ukkonen const &u, Word const &w)
	Check if a word is a suffix of any word in a suffix tree.

bool	is_suffix (Ukkonen const &u, word_type const &w)
	Check if a word is a suffix of any word in a suffix tree.

bool	is_suffix_no_checks (Ukkonen const &u, char const *w)
	Check if a word is a suffix of any word in a suffix tree.

template<typename Iterator>
bool	is_suffix_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Check if a word is a suffix of any word in a suffix tree.

template<typename Word>
bool	is_suffix_no_checks (Ukkonen const &u, Word const &w)
	Check if a word is a suffix of any word in a suffix tree.

bool	is_suffix_no_checks (Ukkonen const &u, word_type const &w)
	Check if a word is a suffix of any word in a suffix tree.

size_t	length_maximal_piece_prefix (Ukkonen const &u, char const *w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
size_t	length_maximal_piece_prefix (Ukkonen const &u, Iterator first, Iterator last)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
size_t	length_maximal_piece_prefix (Ukkonen const &u, Word const &w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_prefix (Ukkonen const &u, word_type const &w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_prefix_no_checks (Ukkonen const &u, char const *w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
size_t	length_maximal_piece_prefix_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
size_t	length_maximal_piece_prefix_no_checks (Ukkonen const &u, Word const &w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_prefix_no_checks (Ukkonen const &u, word_type const &w)
	Find the length of the maximal prefix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_suffix (Ukkonen const &u, char const *w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
size_t	length_maximal_piece_suffix (Ukkonen const &u, Iterator first, Iterator last)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
size_t	length_maximal_piece_suffix (Ukkonen const &u, Word const &w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_suffix (Ukkonen const &u, word_type const &w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_suffix_no_checks (Ukkonen const &u, char const *w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
size_t	length_maximal_piece_suffix_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
size_t	length_maximal_piece_suffix_no_checks (Ukkonen const &u, Word const &w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

size_t	length_maximal_piece_suffix_no_checks (Ukkonen const &u, word_type const &w)
	Find the length of the maximal suffix of a word occurring in two different places in a word in a suffix tree.

char const *	maximal_piece_prefix (Ukkonen const &u, char const *w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
Iterator	maximal_piece_prefix (Ukkonen const &u, Iterator first, Iterator last)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
Word::const_iterator	maximal_piece_prefix (Ukkonen const &u, Word const &w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

word_type::const_iterator	maximal_piece_prefix (Ukkonen const &u, word_type const &w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

char const *	maximal_piece_prefix_no_checks (Ukkonen const &u, char const *w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
Iterator	maximal_piece_prefix_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
Word::const_iterator	maximal_piece_prefix_no_checks (Ukkonen const &u, Word const &w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

word_type::const_iterator	maximal_piece_prefix_no_checks (Ukkonen const &u, word_type const &w)
	Find the maximal prefix of a word occurring in two different places in a word in a suffix tree.

char const *	maximal_piece_suffix (Ukkonen const &u, char const *w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
Iterator	maximal_piece_suffix (Ukkonen const &u, Iterator first, Iterator last)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
Word::const_iterator	maximal_piece_suffix (Ukkonen const &u, Word const &w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

word_type::const_iterator	maximal_piece_suffix (Ukkonen const &u, word_type const &w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

char const *	maximal_piece_suffix_no_checks (Ukkonen const &u, char const *w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Iterator>
Iterator	maximal_piece_suffix_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

template<typename Word>
Word::const_iterator	maximal_piece_suffix_no_checks (Ukkonen const &u, Word const &w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

word_type::const_iterator	maximal_piece_suffix_no_checks (Ukkonen const &u, word_type const &w)
	Find the maximal suffix of a word occurring in two different places in a word in a suffix tree.

size_t	number_of_distinct_subwords (Ukkonen const &u)
	Returns the number of distinct subwords of the words in a suffix tree.

size_t	number_of_pieces (Ukkonen const &u, char const *w)
	Find the number of pieces in a decomposition of a word (if any).

template<typename Iterator>
size_t	number_of_pieces (Ukkonen const &u, Iterator first, Iterator last)
	Find the number of pieces in a decomposition of a word (if any).

template<typename Word>
size_t	number_of_pieces (Ukkonen const &u, Word const &w)
	Find the number of pieces in a decomposition of a word (if any).

size_t	number_of_pieces (Ukkonen const &u, word_type const &w)
	Find the number of pieces in a decomposition of a word (if any).

size_t	number_of_pieces_no_checks (Ukkonen const &u, char const *w)
	Find the number of pieces in a decomposition of a word (if any).

template<typename Iterator>
size_t	number_of_pieces_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the number of pieces in a decomposition of a word (if any).

template<typename Word>
size_t	number_of_pieces_no_checks (Ukkonen const &u, Word const &w)
	Find the number of pieces in a decomposition of a word (if any).

size_t	number_of_pieces_no_checks (Ukkonen const &u, word_type const &w)
	Find the number of pieces in a decomposition of a word (if any).

std::vector< std::string >	pieces (Ukkonen const &u, char const *w)
	Find the pieces in a decomposition of a word (if any).

template<typename Iterator>
std::vector< Iterator >	pieces (Ukkonen const &u, Iterator first, Iterator last)
	Find the pieces in a decomposition of a word (if any).

template<typename Word>
std::vector< Word >	pieces (Ukkonen const &u, Word const &w)
	Find the pieces in a decomposition of a word (if any).

std::vector< word_type >	pieces (Ukkonen const &u, word_type const &w)
	Find the pieces in a decomposition of a word (if any).

std::vector< std::string >	pieces_no_checks (Ukkonen const &u, char const *w)
	Find the pieces in a decomposition of a word (if any).

template<typename Iterator>
std::vector< Iterator >	pieces_no_checks (Ukkonen const &u, Iterator first, Iterator last)
	Find the pieces in a decomposition of a word (if any).

template<typename Word>
std::vector< Word >	pieces_no_checks (Ukkonen const &u, Word const &w)
	Find the pieces in a decomposition of a word (if any).

std::vector< word_type >	pieces_no_checks (Ukkonen const &u, word_type const &w)
	Find the pieces in a decomposition of a word (if any).

std::pair< Ukkonen::State, char const * >	traverse (Ukkonen const &u, char const *w)
	Traverse the suffix tree from the root.

template<typename Word>
auto	traverse (Ukkonen const &u, Word const &w)
	Traverse the suffix tree from the root.

std::pair< Ukkonen::State, word_type::const_iterator >	traverse (Ukkonen const &u, word_type const &w)
	Traverse the suffix tree from the root.

char const *	traverse (Ukkonen::State &st, Ukkonen const &u, char const *w)
	Traverse the suffix tree from the root.

template<typename Word>
auto	traverse (Ukkonen::State &st, Ukkonen const &u, Word const &w)
	Traverse the suffix tree from the root.

word_type::const_iterator	traverse (Ukkonen::State &st, Ukkonen const &u, word_type const &w)
	Traverse the suffix tree from the root.

std::pair< Ukkonen::State, char const * >	traverse_no_checks (Ukkonen const &u, char const *w)
	Traverse the suffix tree from the root.

template<typename Word>
auto	traverse_no_checks (Ukkonen const &u, Word const &w)
	Traverse the suffix tree from the root.

std::pair< Ukkonen::State, word_type::const_iterator >	traverse_no_checks (Ukkonen const &u, word_type const &w)
	Traverse the suffix tree from the root.

char const *	traverse_no_checks (Ukkonen::State &st, Ukkonen const &u, char const *w)
	Traverse the suffix tree from the root.

template<typename Word>
auto	traverse_no_checks (Ukkonen::State &st, Ukkonen const &u, Word const &w)
	Traverse the suffix tree from the root. .

word_type::const_iterator	traverse_no_checks (Ukkonen::State &st, Ukkonen const &u, word_type const &w)
	Traverse the suffix tree from the root.

Function Documentation

◆ add_word() [1/4]

void add_word	(	Ukkonen &	u,
		char const *	w )

See add_word_no_checks.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ add_word() [2/4]

template<typename Iterator>

void add_word	(	Ukkonen &	u,
		Iterator	first,
		Iterator	last )

See add_word_no_checks.

Exceptions

LibsemigroupsException if throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ add_word() [3/4]

template<typename Word>

void add_word	(	Ukkonen &	u,
		Word const &	w )

See add_word_no_checks.

Exceptions

LibsemigroupsException if throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ add_word() [4/4]

void add_word	(	Ukkonen &	u,
		word_type const &	w )

See add_word_no_checks.

Exceptions

LibsemigroupsException if throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ add_word_no_checks() [1/4]

void add_word_no_checks	(	Ukkonen &	u,
		char const *	w )

See add_word_no_checks.

◆ add_word_no_checks() [2/4]

template<typename Iterator>

void add_word_no_checks	(	Ukkonen &	u,
		Iterator	first,
		Iterator	last )

See add_word_no_checks.

◆ add_word_no_checks() [3/4]

template<typename Word>

void add_word_no_checks	(	Ukkonen &	u,
		Word const &	w )

See add_word_no_checks.

◆ add_word_no_checks() [4/4]

void add_word_no_checks	(	Ukkonen &	u,
		word_type const &	w )

See add_word_no_checks.

◆ add_words() [1/2]

template<typename Iterator1, typename Iterator2>

void add_words	(	Ukkonen &	u,
		Iterator1	first,
		Iterator2	last )

See add_words_no_checks(Ukkonen&, Iterator1, Iterator2).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws for any w in [first, last).

See also: throw_if_contains_unique_letter.

◆ add_words() [2/2]

void add_words	(	Ukkonen &	u,
		std::vector< word_type > const &	words )

See vector<word_type> const&).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws for any w in words.

See also: throw_if_contains_unique_letter.

◆ add_words_no_checks() [1/2]

template<typename Iterator1, typename Iterator2>

void add_words_no_checks	(	Ukkonen &	u,
		Iterator1	first,
		Iterator2	last )

Add all words in a range to a Ukkonen object.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ add_words_no_checks() [2/2]

void add_words_no_checks	(	Ukkonen &	u,
		std::vector< word_type > const &	words )

Add all words in a std::vector to a Ukkonen object.

Parameters

u	the Ukkonen object.
words	the words to add.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ dfs()

template<typename T>

auto dfs	(	Ukkonen const &	u,
		T &	helper )

This function can be used to perform a depth first search in the suffix tree u. The 2nd parameter is a helper object that must implement:

A function void pre_order(Ukkonen const& u, size_t i);
A function void post_order(Ukkonen const& u, size_t i); and
A function auto yield(Ukkonen const& u).

The function T::pre_order is called when the node n with index i is first encountered in the depth-first search, and the function T::post_order is called when the subtree rooted at n has been completely explored.

The function yield is called at the end of the depth-first search and its return value is returned by this function.

Template Parameters

T	the type of the helper object.

Parameters

u	the Ukkonen object.
helper	the helper object.

Returns: A value whose type is the same as the return type of T::yield.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ dot()

Dot dot ( Ukkonen const & u )

nodiscard

This function returns a Dot object representing the suffix tree defined by u.

Internally, all words added to the suffix tree are stored as a single string delimited by unique letters. The edge labels present in this Dot object correspond to intervals of letters in that delimited string.

Parameters

u	the Ukkonen object.

Returns: A Dot object.

Exceptions

LibsemigroupsException	if `u` does not contain any words.
LibsemigroupsException	if the number of words in `u` is greater than 24.

◆ is_piece() [1/4]

bool is_piece	(	Ukkonen const &	u,
		char const *	w )

inline

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ is_piece() [2/4]

template<typename Iterator>

bool is_piece	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ is_piece() [3/4]

template<typename Word>

bool is_piece	(	Ukkonen const &	u,
		Word const &	w )

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ is_piece() [4/4]

bool is_piece	(	Ukkonen const &	u,
		word_type const &	w )

inline

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ is_piece_no_checks() [1/4]

bool is_piece_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_piece_no_checks() [2/4]

template<typename Iterator>

bool is_piece_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns true if the word corresponding to first and last that occurs in at least \(2\) different (possibly overlapping) places in the words contained in u. If no such prefix exists, then false is returned.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ is_piece_no_checks() [3/4]

template<typename Word>

bool is_piece_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_piece_no_checks() [4/4]

bool is_piece_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_subword() [1/4]

bool is_subword	(	Ukkonen const &	u,
		char const *	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ is_subword() [2/4]

template<typename Iterator>

bool is_subword	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ is_subword() [3/4]

template<typename Word>

bool is_subword	(	Ukkonen const &	u,
		Word const &	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ is_subword() [4/4]

bool is_subword	(	Ukkonen const &	u,
		word_type const &	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ is_subword_no_checks() [1/4]

bool is_subword_no_checks	(	Ukkonen const &	u,
		char const *	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_subword_no_checks() [2/4]

template<typename Iterator>

bool is_subword_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns true if the word corresponding to first and last is a subword of one of the words in the suffix tree represented by the Ukkonen instance u.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ is_subword_no_checks() [3/4]

template<typename Word>

bool is_subword_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_subword_no_checks() [4/4]

bool is_subword_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_suffix() [1/4]

bool is_suffix	(	Ukkonen const &	u,
		char const *	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ is_suffix() [2/4]

template<typename Iterator>

bool is_suffix	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ is_suffix() [3/4]

template<typename Word>

bool is_suffix	(	Ukkonen const &	u,
		Word const &	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.begin(), w.end()) throws.

See also: throw_if_contains_unique_letter.

◆ is_suffix() [4/4]

bool is_suffix	(	Ukkonen const &	u,
		word_type const &	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ is_suffix_no_checks() [1/4]

bool is_suffix_no_checks	(	Ukkonen const &	u,
		char const *	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_suffix_no_checks() [2/4]

template<typename Iterator>

bool is_suffix_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns true if the word corresponding to first and last is a suffix of one of the words in the suffix tree represented by the Ukkonen instance u.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ is_suffix_no_checks() [3/4]

template<typename Word>

bool is_suffix_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ is_suffix_no_checks() [4/4]

bool is_suffix_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_prefix() [1/4]

size_t length_maximal_piece_prefix	(	Ukkonen const &	u,
		char const *	w )

inline

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_prefix() [2/4]

template<typename Iterator>

size_t length_maximal_piece_prefix	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_prefix() [3/4]

template<typename Word>

size_t length_maximal_piece_prefix	(	Ukkonen const &	u,
		Word const &	w )

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_prefix() [4/4]

size_t length_maximal_piece_prefix	(	Ukkonen const &	u,
		word_type const &	w )

inline

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_prefix_no_checks() [1/4]

size_t length_maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_prefix_no_checks() [2/4]

template<typename Iterator>

size_t length_maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns the length of the maximal length prefix of the word corresponding to first and last that occurs in at least \(2\) different (possibly overlapping) places in the words contained in u. If no such prefix exists, then 0 is returned.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type Iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ length_maximal_piece_prefix_no_checks() [3/4]

template<typename Word>

size_t length_maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_prefix_no_checks() [4/4]

size_t length_maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See length_maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_suffix() [1/4]

size_t length_maximal_piece_suffix	(	Ukkonen const &	u,
		char const *	w )

inline

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_suffix() [2/4]

template<typename Iterator>

size_t length_maximal_piece_suffix	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_suffix() [3/4]

template<typename Word>

size_t length_maximal_piece_suffix	(	Ukkonen const &	u,
		Word const &	w )

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_suffix() [4/4]

size_t length_maximal_piece_suffix	(	Ukkonen const &	u,
		word_type const &	w )

inline

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ length_maximal_piece_suffix_no_checks() [1/4]

size_t length_maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_suffix_no_checks() [2/4]

template<typename Iterator>

size_t length_maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns the length of the maximal length prefix of the word corresponding to first and last that occurs in at least \(2\) different (possibly overlapping) places in the words contained in u. If no such prefix exists, then 0 is returned.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type Iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ length_maximal_piece_suffix_no_checks() [3/4]

template<typename Word>

size_t length_maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ length_maximal_piece_suffix_no_checks() [4/4]

size_t length_maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_prefix() [1/4]

char const * maximal_piece_prefix	(	Ukkonen const &	u,
		char const *	w )

inline

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_prefix() [2/4]

template<typename Iterator>

Iterator maximal_piece_prefix	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_prefix() [3/4]

template<typename Word>

Word::const_iterator maximal_piece_prefix	(	Ukkonen const &	u,
		Word const &	w )

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_prefix() [4/4]

word_type::const_iterator maximal_piece_prefix	(	Ukkonen const &	u,
		word_type const &	w )

inline

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_prefix_no_checks() [1/4]

char const * maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_prefix_no_checks() [2/4]

template<typename Iterator>

Iterator maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns an iterator pointing one past the last letter in the maximal length prefix of the word corresponding to first and last that occurs in at least \(2\) different (possibly overlapping) places in the words contained in u. If no such prefix exists, then first is returned.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type Iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ maximal_piece_prefix_no_checks() [3/4]

template<typename Word>

Word::const_iterator maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_prefix_no_checks() [4/4]

word_type::const_iterator maximal_piece_prefix_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_suffix() [1/4]

char const * maximal_piece_suffix	(	Ukkonen const &	u,
		char const *	w )

inline

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_suffix() [2/4]

template<typename Iterator>

Iterator maximal_piece_suffix	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_suffix() [3/4]

template<typename Word>

Word::const_iterator maximal_piece_suffix	(	Ukkonen const &	u,
		Word const &	w )

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_suffix() [4/4]

word_type::const_iterator maximal_piece_suffix	(	Ukkonen const &	u,
		word_type const &	w )

inline

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ maximal_piece_suffix_no_checks() [1/4]

char const * maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_suffix_no_checks() [2/4]

template<typename Iterator>

Iterator maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns an iterator pointing at the first letter in the maximal length suffix of the word corresponding to first and last that occurs in at least \(2\) different (possibly overlapping) places in the words contained in u. If no such suffix exists, then first is returned.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type Iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(m ^ 2)\) or \(O(n)\) where \(m\) is the distance between first and last and \(n\) is the return value of Ukkonen::length_of_distinct_words.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ maximal_piece_suffix_no_checks() [3/4]

template<typename Word>

Word::const_iterator maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ maximal_piece_suffix_no_checks() [4/4]

word_type::const_iterator maximal_piece_suffix_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator).

◆ number_of_distinct_subwords()

size_t number_of_distinct_subwords ( Ukkonen const & u )

Returns the total number of distinct subwords of the words in the suffix tree u.

Parameters

u	the Ukkonen object.

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in Ukkonen::length_of_distinct_words.

◆ number_of_pieces() [1/4]

size_t number_of_pieces	(	Ukkonen const &	u,
		char const *	w )

inline

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ number_of_pieces() [2/4]

template<typename Iterator>

size_t number_of_pieces	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ number_of_pieces() [3/4]

template<typename Word>

size_t number_of_pieces	(	Ukkonen const &	u,
		Word const &	w )

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ number_of_pieces() [4/4]

size_t number_of_pieces	(	Ukkonen const &	u,
		word_type const &	w )

inline

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ number_of_pieces_no_checks() [1/4]

size_t number_of_pieces_no_checks	(	Ukkonen const &	u,
		char const *	w )

inline

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ number_of_pieces_no_checks() [2/4]

template<typename Iterator>

size_t number_of_pieces_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns minimum number of pieces whose product equals the word corresponding to first and last if such a product exists, and 0 if no such product exists. Recall that a piece is a word that occurs in two distinct positions (possibly overlapping) of the words in the suffix tree u.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ number_of_pieces_no_checks() [3/4]

template<typename Word>

size_t number_of_pieces_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ number_of_pieces_no_checks() [4/4]

size_t number_of_pieces_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

inline

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ pieces() [1/4]

std::vector< std::string > pieces	(	Ukkonen const &	u,
		char const *	w )

inline

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

◆ pieces() [2/4]

template<typename Iterator>

std::vector< Iterator > pieces	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(first, last) throws.

See also: throw_if_contains_unique_letter.

◆ pieces() [3/4]

template<typename Word>

std::vector< Word > pieces	(	Ukkonen const &	u,
		Word const &	w )

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ pieces() [4/4]

std::vector< word_type > pieces	(	Ukkonen const &	u,
		word_type const &	w )

inline

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w) throws.

See also: throw_if_contains_unique_letter.

◆ pieces_no_checks() [1/4]

std::vector< std::string > pieces_no_checks	(	Ukkonen const &	u,
		char const *	w )

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ pieces_no_checks() [2/4]

template<typename Iterator>

std::vector< Iterator > pieces_no_checks	(	Ukkonen const &	u,
		Iterator	first,
		Iterator	last )

Returns a std::vector of iterators pointing one past the last letter in the pieces whose product equals the word corresponding to first and last if such a product exists, and an empty std::vector if no such product exists. Recall that a piece is a word that occurs in two distinct positions (possibly overlapping) of the words in the suffix tree u.

Template Parameters

Iterator the type of the 2nd and 3rd parameters.

Parameters

u	the Ukkonen object.
first	iterator pointing to the first letter of the word.
last	one beyond the last letter of the word.

Returns: A value of type std::vector<Iterator>.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the distance between first and last.

Warning: This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.

◆ pieces_no_checks() [3/4]

template<typename Word>

std::vector< Word > pieces_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ pieces_no_checks() [4/4]

std::vector< word_type > pieces_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

◆ traverse() [1/6]

std::pair< Ukkonen::State, char const * > traverse	(	Ukkonen const &	u,
		char const *	w )

See traverse_no_checks(Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ traverse() [2/6]

template<typename Word>

auto traverse	(	Ukkonen const &	u,
		Word const &	w )

See traverse_no_checks(Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ traverse() [3/6]

std::pair< Ukkonen::State, word_type::const_iterator > traverse	(	Ukkonen const &	u,
		word_type const &	w )

See traverse_no_checks(Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ traverse() [4/6]

char const * traverse	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		char const *	w )

See State&, Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w, w + std::strlen(w)) throws.

See also: throw_if_contains_unique_letter.

◆ traverse() [5/6]

template<typename Word>

auto traverse	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		Word const &	w )

See State&, Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ traverse() [6/6]

word_type::const_iterator traverse	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		word_type const &	w )

See State&, Iterator, Iterator) const.

Exceptions

LibsemigroupsException if u.throw_if_contains_unique_letter(w.cbegin(), w.cend()) throws.

See also: throw_if_contains_unique_letter.

◆ traverse_no_checks() [1/6]

std::pair< Ukkonen::State, char const * > traverse_no_checks	(	Ukkonen const &	u,
		char const *	w )

See traverse_no_checks(Iterator, Iterator) const.

◆ traverse_no_checks() [2/6]

template<typename Word>

auto traverse_no_checks	(	Ukkonen const &	u,
		Word const &	w )

See traverse_no_checks(Iterator, Iterator) const.

◆ traverse_no_checks() [3/6]

std::pair< Ukkonen::State, word_type::const_iterator > traverse_no_checks	(	Ukkonen const &	u,
		word_type const &	w )

See traverse_no_checks(Iterator, Iterator) const.

◆ traverse_no_checks() [4/6]

char const * traverse_no_checks	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		char const *	w )

See State&, Iterator, Iterator) const.

◆ traverse_no_checks() [5/6]

template<typename Word>

auto traverse_no_checks	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		Word const &	w )

See State&, Iterator, Iterator) const.

◆ traverse_no_checks() [6/6]

word_type::const_iterator traverse_no_checks	(	Ukkonen::State &	st,
		Ukkonen const &	u,
		word_type const &	w )

See State&, Iterator, Iterator) const.

Functions

Function Documentation

◆ add_word() [1/4]

◆ add_word() [2/4]

◆ add_word() [3/4]

◆ add_word() [4/4]

◆ add_word_no_checks() [1/4]

◆ add_word_no_checks() [2/4]

◆ add_word_no_checks() [3/4]

◆ add_word_no_checks() [4/4]

◆ add_words() [1/2]

◆ add_words() [2/2]

◆ add_words_no_checks() [1/2]

◆ add_words_no_checks() [2/2]

◆ dfs()

◆ dot()

◆ is_piece() [1/4]

◆ is_piece() [2/4]

◆ is_piece() [3/4]

◆ is_piece() [4/4]

◆ is_piece_no_checks() [1/4]

◆ is_piece_no_checks() [2/4]

◆ is_piece_no_checks() [3/4]

◆ is_piece_no_checks() [4/4]

◆ is_subword() [1/4]

◆ is_subword() [2/4]

◆ is_subword() [3/4]

◆ is_subword() [4/4]

◆ is_subword_no_checks() [1/4]

◆ is_subword_no_checks() [2/4]

◆ is_subword_no_checks() [3/4]

◆ is_subword_no_checks() [4/4]

◆ is_suffix() [1/4]

◆ is_suffix() [2/4]

◆ is_suffix() [3/4]

◆ is_suffix() [4/4]

◆ is_suffix_no_checks() [1/4]

◆ is_suffix_no_checks() [2/4]

◆ is_suffix_no_checks() [3/4]

◆ is_suffix_no_checks() [4/4]

◆ length_maximal_piece_prefix() [1/4]

◆ length_maximal_piece_prefix() [2/4]

◆ length_maximal_piece_prefix() [3/4]

◆ length_maximal_piece_prefix() [4/4]

◆ length_maximal_piece_prefix_no_checks() [1/4]

◆ length_maximal_piece_prefix_no_checks() [2/4]

◆ length_maximal_piece_prefix_no_checks() [3/4]

◆ length_maximal_piece_prefix_no_checks() [4/4]

◆ length_maximal_piece_suffix() [1/4]

◆ length_maximal_piece_suffix() [2/4]

◆ length_maximal_piece_suffix() [3/4]

◆ length_maximal_piece_suffix() [4/4]

◆ length_maximal_piece_suffix_no_checks() [1/4]

◆ length_maximal_piece_suffix_no_checks() [2/4]

◆ length_maximal_piece_suffix_no_checks() [3/4]

◆ length_maximal_piece_suffix_no_checks() [4/4]

◆ maximal_piece_prefix() [1/4]

◆ maximal_piece_prefix() [2/4]

◆ maximal_piece_prefix() [3/4]

◆ maximal_piece_prefix() [4/4]

◆ maximal_piece_prefix_no_checks() [1/4]

◆ maximal_piece_prefix_no_checks() [2/4]

◆ maximal_piece_prefix_no_checks() [3/4]

◆ maximal_piece_prefix_no_checks() [4/4]

◆ maximal_piece_suffix() [1/4]

◆ maximal_piece_suffix() [2/4]

◆ maximal_piece_suffix() [3/4]

◆ maximal_piece_suffix() [4/4]

◆ maximal_piece_suffix_no_checks() [1/4]

◆ maximal_piece_suffix_no_checks() [2/4]

◆ maximal_piece_suffix_no_checks() [3/4]

◆ maximal_piece_suffix_no_checks() [4/4]

◆ number_of_distinct_subwords()

◆ number_of_pieces() [1/4]

◆ number_of_pieces() [2/4]

◆ number_of_pieces() [3/4]

◆ number_of_pieces() [4/4]

◆ number_of_pieces_no_checks() [1/4]

◆ number_of_pieces_no_checks() [2/4]

◆ number_of_pieces_no_checks() [3/4]