a bit of data structure: Suffix Array

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