Skip to content

suffixTreeUkkonen ​

suffixTreeUkkonen(text: string): SuffixTree constrói uma suffix tree sobre text usando o algoritmo linear de Ukkonen. A SuffixTree retornada é um handle de propriedade do chamador de tyrus:algorithm; ela expõe getSuffixArray(), que devolve o índice inicial de cada sufixo de text, ordenados lexicograficamente pela comparação dos bytes do sufixo, como um array novo de propriedade do chamador com uma entrada por caractere da entrada.

Construção ​

SintaxeDescrição
suffixTreeUkkonen(text: string)Construir uma suffix tree sobre text

Métodos ​

MétodoAssinaturaRetornaDescrição
getSuffixArray() => usize[]usize[]Índice inicial de cada sufixo, ordenados lexicograficamente

Complexidade ​

OperaçãoComplexidade Temporal
construçãoO(n), algoritmo de Ukkonen
getSuffixArrayO(n), uma única travessia da árvore
memóriaO(n)

Exemplos ​

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

vazio e um único caractere ​

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

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

importação por namespace ​

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

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