Skip to content

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 ​

AssinaturaRetornaDescrição
suffixArray(text: string)usize[]Índice inicial de cada sufixo, ordenado lexicograficamente

Complexidade ​

OperaçãoComplexidade Temporal
construçãoO(n² log n), ordenação direta de sufixos
memóriaO(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]);  // 2

Resultado 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); // 14

sortRoundCount 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.