suffix_array.md

Suffix Array

A suffix array is a sorted array of all suffixes of a string.

	Average	Worst case
Space	O(n)	O(n)
Construction	O(n)	O(n)

Definition

The suffix array $$A$$ of $$S$$ is defined to be an array of integers providing the starting positions of suffixes of $$S$$ in lexicograhical order.