Skip to content

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 ​

SignatureReturnsDescription
suffixArray(text: string)usize[]Starting index of every suffix, sorted lexicographically

Complexity ​

OperationTime Complexity
constructionO(n² log n), direct suffix sorting
memoryO(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]);  // 2

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

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