Editing Suffix array (section)

== Example ==

Consider the text <math>S</math>=<code>banana$</code> to be indexed:
{| class="wikitable"
|-
! {{left header}} | i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! {{left header}} | <math>S[i]</math>
| b || a || n || a || n || a || $
|}

The text ends with the special sentinel letter <code>$</code> that is unique and lexicographically smaller than any other character. The text has the following suffixes:

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|-  class="even"
|  align="left" | ana$ ||  align="left" | 4
|-  class="odd"
|  align="left" | na$ ||  align="left" | 5
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|}

These suffixes can be sorted in ascending order:

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="even"
|  align="left" | ana$ ||  align="left" | 4
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="odd"
|  align="left" | na$ ||  align="left" | 5
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|}

The suffix array <math>A</math> contains the starting positions of these sorted suffixes:

{| class="wikitable"
! {{left header}} | i =
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! {{left header}} | <math>A[i]</math> =
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|}

The suffix array with the suffixes written out vertically underneath for clarity:

{| class="wikitable"
! {{left header}} | i =
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! {{left header}} | <math>A[i]</math> =
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|-
! {{left header}} | 1
| $ || a || a || a || b || n || n
|-
! {{left header}} | 2
|   || $ || n || n || a || a || a
|-
! {{left header}} | 3
|   ||   || a || a || n || $ || n
|-
! {{left header}} | 4
|   ||   || $ || n || a ||  || a
|-
! {{left header}} | 5
|   ||   ||  || a || n ||  || $
|-
! {{left header}} | 6
|   ||   ||  || $ || a ||  || 
|-
! {{left header}} | 7
|   ||   ||  ||  || $ ||  ||

|}

So for example, <math>A[3]</math> contains the value 4, and therefore refers to the suffix starting at position 4 within <math>S</math>, which is the suffix <code>ana$</code>.