Skip to content

suffixArray ​

suffixArray(text: string): usize[] devuelve el índice inicial de cada sufijo de text, ordenados lexicográficamente comparando los bytes del sufijo. El resultado es un array nuevo de propiedad del llamador, con una entrada por carácter de la entrada; su primer elemento es el índice inicial del sufijo más pequeño. Es una función libre de tyrus:algorithm, importada como cualquier otro nombre de ese módulo.

Función ​

FirmaDevuelveDescripción
suffixArray(text: string)usize[]Índice inicial de cada sufijo, ordenados lexicográficamente

Complejidad ​

OperaciónComplejidad Temporal
construcciónO(n² log n), ordenación directa de sufijos
memoriaO(n)

Ejemplos ​

banana ​

tyrus
import { suffixArray } from "tyrus:algorithm";

const indices = suffixArray("banana");

print(indices);  // [5, 3, 1, 0, 4, 2]

vacío y un único carácter ​

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

const single = suffixArray("a");
print(single);  // [0]

importación por namespace ​

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

const indices = alg.suffixArray("mississippi");
print(indices[0]);   // 10
print(indices[10]);  // 2

Resultado de estudio ​

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 cuenta las rondas del merge bottom-up, comparisonCount cuenta las comparaciones entre sufijos y comparedByteCount cuenta los pares de bytes inspeccionados por esas comparaciones. La instrumentación mantiene almacenamiento adicional O(n) y el mismo límite temporal O(n² log n) en el peor caso de la ordenación directa de sufijos.