Skip to content

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 ​

SyntaxDescription
suffixTreeUkkonen(text: string)Build a suffix tree over text

Methods ​

MethodSignatureReturnsDescription
getSuffixArray() => usize[]usize[]Starting index of every suffix, sorted lexicographically

Complexity ​

OperationTime Complexity
constructionO(n), Ukkonen's algorithm
getSuffixArrayO(n), single traversal of the tree
memoryO(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]);  // 2

empty 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