Skip to content

suffixTreeUkkonen ​

suffixTreeUkkonen(text: string): SuffixTree construye un suffix tree sobre text con el algoritmo lineal de Ukkonen. La SuffixTree devuelta es un handle de propiedad del llamador de tyrus:algorithm; expone getSuffixArray(), que devuelve el índice inicial de cada sufijo de text, ordenados lexicográficamente comparando los bytes del sufijo, como un array nuevo de propiedad del llamador con una entrada por carácter de la entrada.

Construcción ​

SintaxisDescripción
suffixTreeUkkonen(text: string)Construir un suffix tree sobre text

Métodos ​

MétodoFirmaDevuelveDescripción
getSuffixArray() => usize[]usize[]Índice inicial de cada sufijo, ordenados lexicográficamente

Complejidad ​

OperaciónComplejidad Temporal
construcciónO(n), algoritmo de Ukkonen
getSuffixArrayO(n), un único recorrido del árbol
memoriaO(n)

Ejemplos ​

banana ​

tyrus
import { suffixTreeUkkonen } from "tyrus:algorithm";

const tree = suffixTreeUkkonen("banana");
const indices = tree.getSuffixArray();

print(indices);  // [5, 3, 1, 0, 4, 2]

tipo anotado ​

tyrus
import { suffixTreeUkkonen, SuffixTree } from "tyrus:algorithm";

const tree: SuffixTree = suffixTreeUkkonen("mississippi");
print(tree.getSuffixArray()[0]);   // 10
print(tree.getSuffixArray()[10]);  // 2

vacío y un único carácter ​

tyrus
const empty = suffixTreeUkkonen("");
print(empty.getSuffixArray().length);  // 0

const single = suffixTreeUkkonen("a");
print(single.getSuffixArray());  // [0]

importación por namespace ​

tyrus
import * as alg from "tyrus:algorithm";

const indices = alg.suffixTreeUkkonen("cocoa").getSuffixArray();
print(indices[0]);  // 4
print(indices[4]);  // 1