Ukkonen¶

class Ukkonen¶

Defined in ukkonen.hpp.

This class implements Ukkonen’s algorithm for constructing a generalised suffix tree consisting of word_type. The implementation in this class is based on:

https://cp-algorithms.com/string/suffix-tree-ukkonen.html

The suffix tree is updated when the member function add_word is invoked. Every non-duplicate word added to the tree has a unique letter appended to the end. If a duplicate word is added, then the tree is not modified, but the multiplicity of the word is increased.

Many helper functions are provided in the ukkonen namespace.

Constructors¶

`Ukkonen()`	Default constructor.
`Ukkonen(Ukkonen &&) = default`	Default constructor.
`Ukkonen(Ukkonen const &) = default`	Default constructor.
`operator=(Ukkonen &&) = default`	Default constructor.
`operator=(Ukkonen const &) = default`	Default constructor.

Member types¶

`const_iterator`	Alias for `word_type` iterators.
`index_type`
`unique_letter_type`	Alias for any letter that is added by `Ukkonen` (so that unique strings end in unique letters).
`word_index_type`	Alias for order that words were added.

Initialisation¶

`add_word(Iterator,Iterator)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word(Word const &)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word(char const *)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word(const_iterator,const_iterator)`	Check and add a word to the suffix tree.
`add_word(word_type const &)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word_no_checks(Iterator,Iterator)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word_no_checks(Word const &)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word_no_checks(char const *)`	See `add_word_no_checks(const_iterator, const_iterator)`
`add_word_no_checks(const_iterator,const_iterator)`	Add a word to the suffix tree.
`add_word_no_checks(word_type const &)`	See `add_word_no_checks(const_iterator, const_iterator)`

Attributes¶

`length_of_distinct_words() const noexcept`	Returns the sum of the lengths of the distinct words in the suffix tree.
`length_of_words() const noexcept`	Returns the sum of the lengths of all of the words in the suffix tree.
`max_word_length() const noexcept`	Returns the maximum length of word in the suffix tree.
`nodes() const noexcept`	Returns the nodes in the suffix tree.
`number_of_distinct_words() const noexcept`	Returns the number of distinct non-empty words in the suffix tree.
`number_of_words() const noexcept`	Returns the number of non-empty words in the suffix tree.

Iterators¶

`begin() const noexcept`	Returns an iterator pointing to the first letter of the first word in the suffix tree.
`cbegin() const noexcept`	Returns an iterator pointing to the first letter of the first word in the suffix tree.
`cend() const noexcept`	Returns an iterator pointing one past the last letter of the last word in the suffix tree.
`end() const noexcept`	Returns an iterator pointing one past the last letter of the last word in the suffix tree.

Validation¶

`validate_word(Iterator,Iterator) const`	Validate the word `[first, last)`.
`validate_word(word_type const &) const`	Validate a word.

Other member functions¶

`distance_from_root(Node const &) const`	Returns the distance of a node from the root.
`index(Iterator,Iterator) const`	See `index_no_checks` .
`index_no_checks(Iterator,Iterator) const`	Find the index of a word in the suffix tree.
`is_suffix(State const &) const`	Check if a state corresponds to a suffix.
`is_unique_letter(letter_type) const noexcept`	Check if a letter is a unique letter added to the end of a word in the suffix tree.
`multiplicity(word_index_type) const`	Returns the multiplicity of a word by index.
`traverse(Iterator,Iterator) const`	See `traverse_no_checks` .
`traverse(State &,Iterator,Iterator) const`	See `traverse_no_checks` .
`traverse_no_checks(Iterator,Iterator) const`	Traverse the suffix tree from the root.
`traverse_no_checks(State &,Iterator,Iterator) const`	Traverse the suffix tree from the root.
`unique_letter(word_index_type) const noexcept`	Returns the unique letter added to the end of a word in the suffix tree.
`word_index(Node const &) const`	Returns the index of the word corresponding to a node.
`word_index(index_type) const`	Returns the index of the word corresponding to a position.