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

See add_word_no_checks(const_iterator, const_iterator)

template<typename Word>
inline void libsemigroups::Ukkonen::add_word_no_checks(Word const &w)

See add_word_no_checks(const_iterator, const_iterator)

inline void libsemigroups::Ukkonen::add_word_no_checks(char const *w)

See add_word_no_checks(const_iterator, const_iterator)

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

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)

inline void libsemigroups::Ukkonen::add_word_no_checks(word_type const &w)

See add_word_no_checks(const_iterator, const_iterator)