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.