Suffix array: Difference between revisions

Revision as of 18:50, 3 April 2022

Revision as of 19:48, 6 May 2022

Line 32:

Let <math>S=S[1]S[2]...S[n]</math> be an <math display="inline">n</math>-string and let <math>S[i,j]</math> denote the substring of <math>S</math> ranging from <math>i</math> to <math>j</math> inclusive.

The suffix array <math>A</math> of <math>S</math> is now defined to be an array of integers providing the starting positions of [[Suffix (computer science)|suffixes]] of <math>S</math> in [[lexicographical order]]. This means, an entry <math>A[i]</math> contains the starting position of the <math>i</math>-th smallest suffix in <math>S</math> and thus for all <math>1 <\leq i \leq n</math>: <math>S[A[i-1],n] < S[A[i],n]</math>.

Each [[Suffix (computer science)|suffix]] of <math>S</math> shows up in <math>A</math> exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in <math>A</math>.