suffixArray
suffixArray(text: string): usize[] returns the starting index of every suffix of text, sorted lexicographically by comparing the suffix bytes. The result is a fresh array owned by the caller, with one entry per input character; its first element is the starting index of the smallest suffix. It is a free function of tyrus:algorithm, imported like any other name from that module.
Function
| Signature | Returns | Description |
|---|---|---|
suffixArray(text: string) | usize[] | Starting index of every suffix, sorted lexicographically |
Complexity
| Operation | Time Complexity |
|---|---|
| construction | O(n² log n), direct suffix sorting |
| memory | O(n) |
Examples
banana
tyrus
import { suffixArray } from "tyrus:algorithm";
const indices = suffixArray("banana");
print(indices); // [5, 3, 1, 0, 4, 2]empty and single character
tyrus
const empty = suffixArray("");
print(empty.length); // 0
const single = suffixArray("a");
print(single); // [0]namespace import
tyrus
import * as alg from "tyrus:algorithm";
const indices = alg.suffixArray("mississippi");
print(indices[0]); // 10
print(indices[10]); // 2Study result
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 counts bottom-up merge rounds, comparisonCount counts suffix comparisons, and comparedByteCount counts byte pairs inspected by those comparisons. Instrumentation retains O(n) additional storage and the same O(n² log n) worst-case time bound as direct suffix sorting.
