Initialisation¶
This page contains information about the member functions for the Ukkonen
class related to initialisation.
-
template<typename Iterator>
inline void libsemigroups::Ukkonen::add_word(Iterator first, Iterator last)¶ See add_word_no_checks(const_iterator, const_iterator)
- Throws
LibsemigroupsException – if
validate_word(first, last)
throws.
-
template<typename Word>
inline void libsemigroups::Ukkonen::add_word(Word const &w)¶ See add_word_no_checks(const_iterator, const_iterator)
- Throws
LibsemigroupsException – if
validate_word(w)
throws.
-
inline void libsemigroups::Ukkonen::add_word(char const *w)¶
See add_word_no_checks(const_iterator, const_iterator)
- Throws
LibsemigroupsException – if
Ukkonen::validate_word(w, w + std::strlen(w))
throws.
-
inline void libsemigroups::Ukkonen::add_word(const_iterator first, const_iterator last)¶
Check and add a word to the suffix tree.
This function does the same as add_word_no_checks(const_iterator, const_iterator) after first checking that none of the letters in the word corresponding to
first
andlast
is equal to any of the existing unique letters.- Throws
LibsemigroupsException – if
validate_word(first, last)
throws.
-
inline void libsemigroups::Ukkonen::add_word(word_type const &w)¶
See add_word_no_checks(const_iterator, const_iterator)
- Throws
LibsemigroupsException – if
validate_word(w)
throws.
-
template<typename Iterator>
inline void libsemigroups::Ukkonen::add_word_no_checks(Iterator first, Iterator last)¶
-
void libsemigroups::Ukkonen::add_word_no_checks(const_iterator first, const_iterator last)¶
Add a word to the suffix tree.
Calling this function immediately invokes Ukkonen’s algorithm to add the given word to the suffix tree (if it is not already contained in the tree). If an identical word is already in the tree, then this function does nothing except increase the multiplicity of that word. If
first == last
, then this function does nothing.- 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.- Parameters
first – iterator pointing to the first letter of the word to add.
last – one beyond the last letter of the word to add.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)