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()`
`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`
`word_index_type`	Alias for order that words were added.

Initialisation¶

`add_word(Iterator,Iterator)`
`add_word(Word const &)`
`add_word(char const *)`
`add_word(const_iterator,const_iterator)`
`add_word(word_type const &)`
`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_word_no_checks(word_type const &)`	See `add_word_no_checks(const_iterator, const_iterator)` .

Attributes¶

`length_of_distinct_words() const noexcept`
`length_of_words() const noexcept`
`max_word_length() const noexcept`
`nodes() const noexcept`
`number_of_distinct_words() const noexcept`
`number_of_words() const noexcept`

Iterators¶

`begin() const noexcept`
`cbegin() const noexcept`
`cend() const noexcept`
`end() const noexcept`

Validation¶

`validate_word(Iterator,Iterator) const`
`validate_word(word_type const &) const`

Other member functions¶

`distance_from_root(Node const &) const`
`index(Iterator,Iterator) const`
`index_no_checks(Iterator,Iterator) const`
`is_suffix(State const &) const`
`is_unique_letter(letter_type) const noexcept`
`multiplicity(word_index_type) const`
`traverse(Iterator,Iterator) const`
`traverse(State &,Iterator,Iterator) const`
`traverse_no_checks(Iterator,Iterator) const`
`traverse_no_checks(State &,Iterator,Iterator) const`
`unique_letter(word_index_type) const noexcept`
`word_index(Node const &) const`
`word_index(index_type) const`