suffixArray
suffixArray(text: string): usize[] retorna o índice inicial de cada sufixo de text, ordenados lexicograficamente pela comparação dos bytes do sufixo. O resultado é um array novo de propriedade do chamador, com uma entrada por caractere da entrada; seu primeiro elemento é o índice inicial do menor sufixo. É uma função livre de tyrus:algorithm, importada como qualquer outro nome desse módulo.
Função
| Assinatura | Retorna | Descrição |
|---|---|---|
suffixArray(text: string) | usize[] | Índice inicial de cada sufixo, ordenado lexicograficamente |
Complexidade
| Operação | Complexidade Temporal |
|---|---|
| construção | O(n² log n), ordenação direta de sufixos |
| memória | O(n) |
Exemplos
banana
tyrus
import { suffixArray } from "tyrus:algorithm";
const indices = suffixArray("banana");
print(indices); // [5, 3, 1, 0, 4, 2]vazio e um único caractere
tyrus
const empty = suffixArray("");
print(empty.length); // 0
const single = suffixArray("a");
print(single); // [0]importação por namespace
tyrus
import * as alg from "tyrus:algorithm";
const indices = alg.suffixArray("mississippi");
print(indices[0]); // 10
print(indices[10]); // 2Resultado de estudo
tyrus
interface SuffixArrayInfo {
text: string;
suffixArray: usize[];
sortRoundCount: usize;
comparisonCount: usize;
comparedByteCount: usize;
}tyrus
import { SuffixArrayInfo, suffixArrayInfo } from "tyrus:algorithm";
const info: SuffixArrayInfo = suffixArrayInfo("banana");
print(info.text); // banana
print(info.suffixArray); // [5, 3, 1, 0, 4, 2]
print(info.sortRoundCount); // 3
print(info.comparisonCount); // 11
print(info.comparedByteCount); // 14sortRoundCount conta as rodadas do merge bottom-up, comparisonCount conta as comparações entre sufixos e comparedByteCount conta os pares de bytes inspecionados por essas comparações. A instrumentação mantém armazenamento adicional O(n) e o mesmo limite de tempo O(n² log n) no pior caso da ordenação direta de sufixos.
