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
| Sintaxe | Descrição |
|---|---|
suffixTreeUkkonen(text: string) | Construir uma suffix tree sobre text |
Métodos
| Método | Assinatura | Retorna | Descrição |
|---|---|---|---|
getSuffixArray | () => usize[] | usize[] | Índice inicial de cada sufixo, ordenados lexicograficamente |
Complexidade
| Operação | Complexidade Temporal |
|---|---|
| construção | O(n), algoritmo de Ukkonen |
getSuffixArray | O(n), uma única travessia da árvore |
| memória | O(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]); // 2vazio 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