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

My approach is::

- Construct a Suffix Array for the Given string { 0 indexed }.
- Build LCP(longest Common Prefix) from the suffix array { 0 indexed }…
- 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.