TLE in SUBLEX on Spoj

I’m solving following question on SPOJ, link, However it is giving me TLE.
My approach is::

  1. Construct a Suffix Array for the Given string { 0 indexed }.
  2. Build LCP(longest Common Prefix) from the suffix array { 0 indexed }…
  3. Construct an array ind[], where ind[i] gives the Cumulative sum of the Number of substrings that can be constructed if we start at position sa[i] in lexicographical order.

for eg Suppose we have string abba then

suff_arr[] = {3,0,2,1} i.e a,abba,ba,bba

lcp[] = {1,0,1,0}

ind[] = {1,4,6,8}

** i.e ind 1 = 0 & suff_arr[0] = 3(‘a’) which means that if we start at suff__arr[0] we can construct a substring ‘a’ whose lexicographical rank is 1 similarly ind 1 = 4 and suff_ar 1 = 0(abba) so if we start at index 0, we can construct substrings ab,abb,abba whose rank is 2,3,4 respectively **

Now suppose we get K = 5 then we perform binary search on ind[] to get the i where ind[i] <= K.

using this i we look for the starting position for our required array in suff_arr[i] and get the answer after doing some computations and checking corner cases.

//