Suffix array is simply the array of suffixes of a string sorted to their lexicographical order. Easiest way to construct suffix array will have a running time of \(O(N^2\log{N})\).

Pseudo-code for suffix array construction in \(O(N\text{log}^2N)\) time complexity (not the best but not bad):

Let \(A\) be the string

1. Set \(N = \text{length}(A)\)

2. For i from 0 to \(N-1\):

2.1 Set P(0, i) = position of \(A_i\) in A that is sorted by its individual character

3. Set cnt = 1

4. For k from 0 to \(\lceil\text{log}N \rceil\):

4.1 For i from 0 to N-1:

4.1.1 Set L(i) = ( P(k-1, i), P(k-1, i+cnt), i )

4.2 Sort L(i)

4.3 Compute P(k, i) using L(i)

4.4 cnt = cnt * 2