Suffix array: Difference between revisions

Revision as of 23:52, 20 May 2020

Revision as of 23:56, 20 May 2020

Line 37:

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 < 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. Note suffixesSuffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in <math>A</math>.

== Example ==