Suffix Array Induced Sorting (SA-IS)

Suffix

Builds an ordered index of every suffix of one text.

Out-of-Place

Requires auxiliary memory proportional to the input size (O(n)).

Suffix Array

Builds the suffix array of one text by classifying and inducing suffix positions.

Visualize Fullscreen

Text for suffix array

Enter data, then run the algorithm.

Did you know?

LMS means leftmost S-type; ordering these special substrings creates the smaller recursive problem.
SA-IS returns starting positions of suffixes in sorted order, not a rearranged copy of the text.
Before induced sorting, the Unicode wrapper maps distinct code points to compact integer ranks. Sorting that alphabet adds work beyond the linear-time SA-IS core described for integer alphabets.

How it Works

Classify suffix positions as L-type or S-type and locate LMS positions.
Induce a provisional suffix order from LMS seeds.
Rank LMS substrings recursively and induce the final order.

Complexity Analysis

Best Case

O(n + σ log σ)

Average

O(n + σ log σ)

Worst Case

O(n + σ log σ)

Space

O(n + σ)

Advantages

Linear induced-sorting core after alphabet compression.
Useful for indexing and text search.

Disadvantages

Output is suffix positions, not a reordered input string.
Alphabet compression sorts distinct code points first.

Implementation

TypeScript sa-is.ts

import type { StringSortEvent } from './string-variants';

/** SA-IS induced sorting, adapted from AtCoder Library's CC0 implementation. */
export function suffixArrayInducedSort(text: string, events?: StringSortEvent[]) {
	const characters = Array.from(text);
	const alphabet = [...new Set(characters)].sort(
		(left, right) => (left.codePointAt(0) as number) - (right.codePointAt(0) as number)
	);
	const rank = new Map(alphabet.map((character, index) => [character, index]));
	const values = characters.map((character) => rank.get(character) as number);
	return saIs(values, alphabet.length - 1, events, 0);
}

function saIs(
	values: number[],
	upper: number,
	events: StringSortEvent[] | undefined,
	depth: number
): number[] {
	const n = values.length;
	if (n === 0) return [];
	if (n === 1) return [0];
	if (n === 2) return values[0] < values[1] ? [0, 1] : [1, 0];
	const suffixArray = new Array<number>(n).fill(-1);
	const sType = new Array<boolean>(n).fill(false);
	for (let index = n - 2; index >= 0; index--) {
		sType[index] =
			values[index] === values[index + 1] ? sType[index + 1] : values[index] < values[index + 1];
	}
	if (depth === 0) events?.push({ text: 'Classify suffixes as L-type or S-type' });
	const lBounds = new Array<number>(upper + 1).fill(0);
	const sBounds = new Array<number>(upper + 1).fill(0);
	for (let index = 0; index < n; index++) {
		if (sType[index]) lBounds[values[index] + 1]++;
		else sBounds[values[index]]++;
	}
	for (let value = 0; value <= upper; value++) {
		sBounds[value] += lBounds[value];
		if (value < upper) lBounds[value + 1] += sBounds[value];
	}
	function induce(lms: number[]) {
		suffixArray.fill(-1);
		let cursor = [...sBounds];
		for (const position of lms) {
			if (position < n) suffixArray[cursor[values[position]]++] = position;
		}
		cursor = [...lBounds];
		suffixArray[cursor[values[n - 1]]++] = n - 1;
		for (let index = 0; index < n; index++) {
			const position = suffixArray[index];
			if (position >= 1 && !sType[position - 1]) {
				suffixArray[cursor[values[position - 1]]++] = position - 1;
			}
		}
		cursor = [...lBounds];
		for (let index = n - 1; index >= 0; index--) {
			const position = suffixArray[index];
			if (position >= 1 && sType[position - 1]) {
				suffixArray[--cursor[values[position - 1] + 1]] = position - 1;
			}
		}
		if (depth === 0) {
			events?.push({
				text: `Induce L-type and S-type suffix positions from ${lms.length} LMS seeds`,
				suffixOrder: suffixArray.filter((position) => position >= 0)
			});
		}
	}
	const lmsMap = new Array<number>(n + 1).fill(-1);
	const lms: number[] = [];
	for (let index = 1; index < n; index++) {
		if (!sType[index - 1] && sType[index]) {
			lmsMap[index] = lms.length;
			lms.push(index);
		}
	}
	if (depth === 0) events?.push({ text: `Identify ${lms.length} LMS substrings` });
	induce(lms);
	if (lms.length) {
		const orderedLms = suffixArray.filter((position) => position >= 0 && lmsMap[position] !== -1);
		const reduced = new Array<number>(lms.length);
		let reducedUpper = 0;
		reduced[lmsMap[orderedLms[0]]] = 0;
		for (let index = 1; index < lms.length; index++) {
			let left = orderedLms[index - 1];
			let right = orderedLms[index];
			const leftEnd = lmsMap[left] + 1 < lms.length ? lms[lmsMap[left] + 1] : n;
			const rightEnd = lmsMap[right] + 1 < lms.length ? lms[lmsMap[right] + 1] : n;
			let same = leftEnd - left === rightEnd - right;
			if (same) {
				while (left < leftEnd) {
					if (values[left] !== values[right]) break;
					left++;
					right++;
				}
				if (left === n || values[left] !== values[right]) same = false;
			}
			if (!same) reducedUpper++;
			reduced[lmsMap[orderedLms[index]]] = reducedUpper;
		}
		if (depth === 0)
			events?.push({ text: `Name LMS substrings with ${reducedUpper + 1} distinct ranks` });
		const reducedOrder = saIs(reduced, reducedUpper, events, depth + 1);
		for (let index = 0; index < lms.length; index++) orderedLms[index] = lms[reducedOrder[index]];
		induce(orderedLms);
	}
	if (depth === 0) events?.push({ text: 'Suffix array complete', suffixOrder: [...suffixArray] });
	return suffixArray;
}