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 themultiplicity
of the word is increased.Many helper functions are provided in the
ukkonen
namespace.
Constructors¶
Default constructor. |
|
Default constructor. |
|
Default constructor. |
|
Default constructor. |
|
Default constructor. |
Member types¶
Alias for |
|
Alias for any letter that is added by |
|
Alias for order that words were added. |
Initialisation¶
Check and add a word to the suffix tree. |
|
Add a word to the suffix tree. |
|
Attributes¶
Returns the sum of the lengths of the distinct words in the suffix tree. |
|
Returns the sum of the lengths of all of the words in the suffix tree. |
|
Returns the maximum length of word in the suffix tree. |
|
Returns the nodes in the suffix tree. |
|
Returns the number of distinct non-empty words in the suffix tree. |
|
Returns the number of non-empty words in the suffix tree. |
Iterators¶
Returns an iterator pointing to the first letter of the first word in the suffix tree. |
|
Returns an iterator pointing to the first letter of the first word in the suffix tree. |
|
Returns an iterator pointing one past the last letter of the last word in the suffix tree. |
|
Returns an iterator pointing one past the last letter of the last word in the suffix tree. |
Validation¶
Validate the word |
|
Validate a word. |
Other member functions¶
Returns the distance of a node from the root. |
|
See |
|
Find the index of a word in the suffix tree. |
|
Check if a state corresponds to a suffix. |
|
Check if a letter is a unique letter added to the end of a word in the suffix tree. |
|
Returns the multiplicity of a word by index. |
|
See |
|
See |
|
Traverse the suffix tree from the root. |
|
Traverse the suffix tree from the root. |
|
Returns the unique letter added to the end of a word in the suffix tree. |
|
Returns the index of the word corresponding to a node. |
|
Returns the index of the word corresponding to a position. |