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
| Firma | Devuelve | Descripción |
|---|---|---|
suffixArray(text: string) | usize[] | Índice inicial de cada sufijo, ordenados lexicográficamente |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
| construcción | O(n² log n), ordenación directa de sufijos |
| memoria | O(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]); // 2Resultado 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); // 14sortRoundCount 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.
