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
| Sintaxis | Descripción |
|---|---|
suffixTreeUkkonen(text: string) | Construir un suffix tree sobre text |
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
getSuffixArray | () => usize[] | usize[] | Índice inicial de cada sufijo, ordenados lexicográficamente |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
| construcción | O(n), algoritmo de Ukkonen |
getSuffixArray | O(n), un único recorrido del árbol |
| memoria | O(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]); // 2vací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