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 all words in a |
|
Add all words in a range to a |
|
Perform a depth first search in a suffix tree. |
|
Returns a string containing a GraphViz representation of a suffix tree. |
|
Check if a word is a piece. |
|
Check if a word is a piece. |
|
Check if a word is a subword of any word in a suffix tree. |
|
Check if a word is a subword of any word in a suffix tree. |
|
Check if a word is a suffix of any word in a suffix tree. |
|
Check if a word is a suffix of any word in a suffix tree. |
|
Find the length of the maximal piece prefix of a word. |
|
Find the length of the maximal piece prefix of a word. |
|
Find the length of the maximal piece suffix of a word. |
|
Find the length of the maximal piece suffix of a word. |
|
Find the maximal piece prefix of a word. |
|
Find the maximal piece prefix of a word. |
|
Find the maximal piece suffix of a word. |
|
Find the maximal piece suffix of a word. |
|
Returns the number of distinct subwords of the words in a suffix tree. |
|
Find the number of pieces in a decomposition of a word (if any). |
|
Find the number of pieces in a decomposition of a word (if any). |
|
Find the pieces in a decomposition of a word (if any). |
|
Find the pieces in a decomposition of a word (if any). |
|
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
andlast
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
andlast
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 anyw
inwords
.
-
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 anyw
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 tofirst
andlast
is a subword of one of the words in the suffix tree represented by the Ukkonen instanceu
.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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 tofirst
andlast
is a suffix of one of the words in the suffix tree represented by the Ukkonen instanceu
.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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
andlast
that occurs in at least \(2\) different (possibly overlapping) places in the words contained inu
. If no such prefix exists, thenfirst
is returned.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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
andlast
that occurs in at least \(2\) different (possibly overlapping) places in the words contained inu
. If no such prefix exists, then0
is returned.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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 tofirst
andlast
that occurs in at least \(2\) different (possibly overlapping) places in the words contained inu
. If no such prefix exists, thenfalse
is returned.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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
andlast
that occurs in at least \(2\) different (possibly overlapping) places in the words contained inu
. If no such suffix exists, thenfirst
is returned.- Complexity
At worst \(O(m ^ 2)\) or \(O(n)\) where \(m\) is the distance between
first
andlast
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
andlast
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
andlast
that occurs in at least \(2\) different (possibly overlapping) places in the words contained inu
. If no such prefix exists, then0
is returned.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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
andlast
if such a product exists, and0
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 treeu
.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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
andlast
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 treeu
.- Complexity
Linear in the distance between
first
andlast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
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 wordsLibsemigroupsException – 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 noden
with indexi
is first encountered in the depth-first search, and the functionT::post_order
is called when the subtree rooted atn
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
.