suffixTreeUkkonen
suffixTreeUkkonen(text: string): SuffixTree builds a suffix tree over text using Ukkonen's linear-time algorithm. The returned SuffixTree is an owned handle of tyrus:algorithm; it exposes getSuffixArray(), which yields the starting index of every suffix of text, sorted lexicographically by comparing the suffix bytes, as a fresh array owned by the caller with one entry per input character.
Construction
| Syntax | Description |
|---|---|
suffixTreeUkkonen(text: string) | Build a suffix tree over text |
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
getSuffixArray | () => usize[] | usize[] | Starting index of every suffix, sorted lexicographically |
Complexity
| Operation | Time Complexity |
|---|---|
| construction | O(n), Ukkonen's algorithm |
getSuffixArray | O(n), single traversal of the tree |
| memory | O(n) |
Examples
banana
tyrus
import { suffixTreeUkkonen } from "tyrus:algorithm";
const tree = suffixTreeUkkonen("banana");
const indices = tree.getSuffixArray();
print(indices); // [5, 3, 1, 0, 4, 2]annotated type
tyrus
import { suffixTreeUkkonen, SuffixTree } from "tyrus:algorithm";
const tree: SuffixTree = suffixTreeUkkonen("mississippi");
print(tree.getSuffixArray()[0]); // 10
print(tree.getSuffixArray()[10]); // 2empty and single character
tyrus
const empty = suffixTreeUkkonen("");
print(empty.getSuffixArray().length); // 0
const single = suffixTreeUkkonen("a");
print(single.getSuffixArray()); // [0]namespace import
tyrus
import * as alg from "tyrus:algorithm";
const indices = alg.suffixTreeUkkonen("cocoa").getSuffixArray();
print(indices[0]); // 4
print(indices[4]); // 1