Recently, I came across the suffix arrays which are a complementary to suffix trees and easier to implement while doing the the LCS question on the spoj the naive algo with complexity O(m*n) is simply unable to pass. So we must apply suffix array to find Longest Common Substring subsequently. SO I googled Suffix Array with finding nohing easy to understand or elseworth simple to write so after much struggle, I have wrote done the code for suffix array in C++, thats easy to understand and implement. Here some theory regarding Suffix Arrays followed by the code

Given a string A = (a0 a1 a2 a3 ….an-1) of length n.

A suffix of string S starting at position i is Suffix(i) = (ai ai+1 ai+2 ….an-1).

There are n suffixes of string A ( starting at each index to the end ).

Let U be a set of suffixes of string A in sorted order. ie obtain all the suffixes of A and sort them to form U.

A suffix array S is an array such that S[i] gives the index of Suffix(i) in U.

for example if A = banana
suffixes of A are:

banana = Suffix(0)

anana = Suffix(1)

nana = Suffix(2)

ana = Suffix(3)

na = Suffix(4)

a = Suffix(5)

after sorting U = {

0 a

1 ana

2 anana

3 banana

4 na

5 nana

}

thus suffix array S would be,

S = { 3, 2, 5, 1, 4, 0 }

S[1] = 2 because index of Suffix(1) = anana in U is 2

Feel free to comment below if you don’t understand this.