Ukkonen helper functions¶

Defined in ukkonen.hpp.

This page contains the documentation for various helper functions for manipulating Ukkonen objects. All such functions are contained in the namespace ukkonen.

Contents¶

`add_words_no_checks()`	Add all words in a `std::vector` to a `Ukkonen` object.
`add_words()`	Add all words in a range to a `Ukkonen` object.
`dfs()`	Perform a depth first search in a suffix tree.
`dot()`	Returns a string containing a GraphViz representation of a suffix tree.
`is_piece_no_checks()`	Check if a word is a piece.
`is_piece()`	Check if a word is a piece.
`is_subword_no_checks()`	Check if a word is a subword of any word in a suffix tree.
`is_subword()`	Check if a word is a subword of any word in a suffix tree.
`is_suffix_no_checks()`	Check if a word is a suffix of any word in a suffix tree.
`is_suffix()`	Check if a word is a suffix of any word in a suffix tree.
`length_maximal_piece_prefix_no_checks()`	Find the length of the maximal piece prefix of a word.
`length_maximal_piece_prefix()`	Find the length of the maximal piece prefix of a word.
`length_maximal_piece_suffix_no_checks()`	Find the length of the maximal piece suffix of a word.
`length_maximal_piece_suffix()`	Find the length of the maximal piece suffix of a word.
`maximal_piece_prefix_no_checks()`	Find the maximal piece prefix of a word.
`maximal_piece_prefix()`	Find the maximal piece prefix of a word.
`maximal_piece_suffix_no_checks()`	Find the maximal piece suffix of a word.
`maximal_piece_suffix()`	Find the maximal piece suffix of a word.
`number_of_distinct_subwords()`	Returns the number of distinct subwords of the words in a suffix tree.
`number_of_pieces_no_checks()`	Find the number of pieces in a decomposition of a word (if any).
`number_of_pieces()`	Find the number of pieces in a decomposition of a word (if any).
`pieces_no_checks()`	Find the pieces in a decomposition of a word (if any).
`pieces()`	Find the pieces in a decomposition of a word (if any).
`traverse()`	Traverse the suffix tree from the root.

Full API¶

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

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

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.

Parameters

u – the Ukkonen object
words – the words to add

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

None

template<typename Iterator> void libsemigroups::ukkonen::add_words_no_checks(Ukkonen &u, Iterator first, Iterator last)¶

Add all words in a range to a Ukkonen object.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

None

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

See add_words_no_checks(Ukkonen&, Iterator, Iterator)

Throws: LibsemigroupsException – if validate_word(w) throws for any w in words.

template<typename Iterator> void libsemigroups::ukkonen::add_words(Ukkonen &u, Iterator first, Iterator last)¶

See add_words_no_checks(Ukkonen&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws for any w in [first, last).

inline auto libsemigroups::ukkonen::traverse(Ukkonen const &u, word_type const &w)¶

See Ukkonen::traverse_no_checks.

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

template<typename Iterator> bool libsemigroups::ukkonen::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.

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type bool.

template<typename Word> bool libsemigroups::ukkonen::is_subword_no_checks(Ukkonen const &u, Word const &w)¶: See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_subword_no_checks(Ukkonen const &u, char const *w)¶: See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_subword_no_checks(Ukkonen const &u, word_type const &w)¶: See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> bool libsemigroups::ukkonen::is_subword(Ukkonen const &u, Iterator first, Iterator last)¶

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> bool libsemigroups::ukkonen::is_subword(Ukkonen const &u, Word const &w)¶

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline bool libsemigroups::ukkonen::is_subword(Ukkonen const &u, char const *w)¶

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

inline bool libsemigroups::ukkonen::is_subword(Ukkonen const &u, word_type const &w)¶

See is_subword_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

template<typename Iterator> bool libsemigroups::ukkonen::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.

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type bool.

template<typename Word> bool libsemigroups::ukkonen::is_suffix_no_checks(Ukkonen const &u, Word const &w)¶: See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_suffix_no_checks(Ukkonen const &u, word_type const &w)¶: See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_suffix_no_checks(Ukkonen const &u, char const *w)¶: See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> bool libsemigroups::ukkonen::is_suffix(Ukkonen const &u, Iterator first, Iterator last)¶

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> bool libsemigroups::ukkonen::is_suffix(Ukkonen const &u, Word const &w)¶

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline bool libsemigroups::ukkonen::is_suffix(Ukkonen const &u, word_type const &w)¶

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline bool libsemigroups::ukkonen::is_suffix(Ukkonen const &u, char const *w)¶

See is_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> Iterator libsemigroups::ukkonen::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.

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type Iterator.

template<typename Word> Word::const_iterator libsemigroups::ukkonen::maximal_piece_prefix_no_checks(Ukkonen const &u, Word const &w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

inline word_type::const_iterator libsemigroups::ukkonen::maximal_piece_prefix_no_checks(Ukkonen const &u, word_type const &w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

inline char const *libsemigroups::ukkonen::maximal_piece_prefix_no_checks(Ukkonen const &u, char const *w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> Iterator libsemigroups::ukkonen::maximal_piece_prefix(Ukkonen const &u, Iterator first, Iterator last)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> Word::const_iterator libsemigroups::ukkonen::maximal_piece_prefix(Ukkonen const &u, Word const &w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline word_type::const_iterator libsemigroups::ukkonen::maximal_piece_prefix(Ukkonen const &u, word_type const &w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline char const *libsemigroups::ukkonen::maximal_piece_prefix(Ukkonen const &u, char const *w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> size_t libsemigroups::ukkonen::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.

Returns 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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type Iterator.

template<typename Word> size_t libsemigroups::ukkonen::length_maximal_piece_prefix_no_checks(Ukkonen const &u, Word const &w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::length_maximal_piece_prefix_no_checks(Ukkonen const &u, word_type const &w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::length_maximal_piece_prefix_no_checks(Ukkonen const &u, char const *w)¶: See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> size_t libsemigroups::ukkonen::length_maximal_piece_prefix(Ukkonen const &u, Iterator first, Iterator last)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> size_t libsemigroups::ukkonen::length_maximal_piece_prefix(Ukkonen const &u, Word const &w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::length_maximal_piece_prefix(Ukkonen const &u, word_type const &w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::length_maximal_piece_prefix(Ukkonen const &u, char const *w)¶

See maximal_piece_prefix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> bool libsemigroups::ukkonen::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).

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type bool.

template<typename Word> bool libsemigroups::ukkonen::is_piece_no_checks(Ukkonen const &u, Word const &w)¶: See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_piece_no_checks(Ukkonen const &u, word_type const &w)¶: See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

inline bool libsemigroups::ukkonen::is_piece_no_checks(Ukkonen const &u, char const *w)¶: See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> bool libsemigroups::ukkonen::is_piece(Ukkonen const &u, Iterator first, Iterator last)¶

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> bool libsemigroups::ukkonen::is_piece(Ukkonen const &u, Word const &w)¶

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline bool libsemigroups::ukkonen::is_piece(Ukkonen const &u, word_type const &w)¶

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline bool libsemigroups::ukkonen::is_piece(Ukkonen const &u, char const *w)¶

See is_piece_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> Iterator libsemigroups::ukkonen::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.

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type Iterator.

template<typename Word> Word::const_iterator libsemigroups::ukkonen::maximal_piece_suffix_no_checks(Ukkonen const &u, Word const &w)¶: See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline word_type::const_iterator libsemigroups::ukkonen::maximal_piece_suffix_no_checks(Ukkonen const &u, word_type const &w)¶: See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline char const *libsemigroups::ukkonen::maximal_piece_suffix_no_checks(Ukkonen const &u, char const *w)¶: See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> Iterator libsemigroups::ukkonen::maximal_piece_suffix(Ukkonen const &u, Iterator first, Iterator last)¶

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> Word::const_iterator libsemigroups::ukkonen::maximal_piece_suffix(Ukkonen const &u, Word const &w)¶

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline word_type::const_iterator libsemigroups::ukkonen::maximal_piece_suffix(Ukkonen const &u, word_type const &w)¶

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline char const *libsemigroups::ukkonen::maximal_piece_suffix(Ukkonen const &u, char const *w)¶

See maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> size_t libsemigroups::ukkonen::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.

Returns 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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type Iterator.

template<typename Word> size_t libsemigroups::ukkonen::length_maximal_piece_suffix_no_checks(Ukkonen const &u, Word const &w)¶: See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::length_maximal_piece_suffix_no_checks(Ukkonen const &u, word_type const &w)¶: See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::length_maximal_piece_suffix_no_checks(Ukkonen const &u, char const *w)¶: See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> size_t libsemigroups::ukkonen::length_maximal_piece_suffix(Ukkonen const &u, Iterator first, Iterator last)¶

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> size_t libsemigroups::ukkonen::length_maximal_piece_suffix(Ukkonen const &u, Word const &w)¶

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::length_maximal_piece_suffix(Ukkonen const &u, word_type const &w)¶

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::length_maximal_piece_suffix(Ukkonen const &u, char const *w)¶

See length_maximal_piece_suffix_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

template<typename Iterator> size_t libsemigroups::ukkonen::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).

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type size_t.

template<typename Word> size_t libsemigroups::ukkonen::number_of_pieces_no_checks(Ukkonen const &u, Word const &w)¶: See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::number_of_pieces_no_checks(Ukkonen const &u, word_type const &w)¶: See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

inline size_t libsemigroups::ukkonen::number_of_pieces_no_checks(Ukkonen const &u, char const *w)¶: See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

template<typename Iterator> size_t libsemigroups::ukkonen::number_of_pieces(Ukkonen const &u, Iterator first, Iterator last)¶

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> size_t libsemigroups::ukkonen::number_of_pieces(Ukkonen const &u, Word const &w)¶

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::number_of_pieces(Ukkonen const &u, word_type const &w)¶

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline size_t libsemigroups::ukkonen::number_of_pieces(Ukkonen const &u, char const *w)¶

See number_of_pieces_no_checks(Ukkonen const&, Iterator, Iterator)

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

size_t libsemigroups::ukkonen::number_of_distinct_subwords(Ukkonen const &u)¶

Returns the number of distinct subwords of the words in a suffix tree.

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

Complexity: Linear in Ukkonen::length_of_distinct_words.

Parameters: u – the Ukkonen object
Throws: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns: A value of type size_t.

template<typename Iterator> std::vector<Iterator> libsemigroups::ukkonen::pieces_no_checks(Ukkonen const &u, Iterator first, Iterator last)¶

Find the pieces in a decomposition of a word (if any).

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.

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.

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.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

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

template<typename Word> std::vector<Word> libsemigroups::ukkonen::pieces_no_checks(Ukkonen const &u, Word const &w)¶: See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

std::vector<word_type> libsemigroups::ukkonen::pieces_no_checks(Ukkonen const &u, word_type const &w)¶: See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

std::vector<std::string> libsemigroups::ukkonen::pieces_no_checks(Ukkonen const &u, char const *w)¶: See pieces_no_checks(Ukkonen const&, Iterator, Iterator).

template<typename Iterator> std::vector<Iterator> libsemigroups::ukkonen::pieces(Ukkonen const &u, Iterator first, Iterator last)¶

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

Throws: LibsemigroupsException – if Ukkonen::validate_word(first, last) throws.

template<typename Word> std::vector<Word> libsemigroups::ukkonen::pieces(Ukkonen const &u, Word const &w)¶

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

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

inline std::vector<word_type> libsemigroups::ukkonen::pieces(Ukkonen const &u, word_type const &w)¶

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

Throws: LibsemigroupsException – if Ukkonen::validate_word(w) throws.

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

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

Throws: LibsemigroupsException – if Ukkonen::validate_word(w, w + std::strlen(w)) throws.

std::string libsemigroups::ukkonen::dot(Ukkonen const &u)¶

Returns a string containing a GraphViz representation of a suffix tree.

Parameters

u – the Ukkonen object

Throws

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

Returns

A value of type std::string.

template<typename T> auto libsemigroups::ukkonen::dfs(Ukkonen const &u, T &helper)¶

Perform a depth first search in a suffix tree.

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)
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

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

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