Hello Everyone!

I was recently studying about suffix arrays and I found myself stuck at this problem. It would be nice if someone explains how to solve this problem.

Thanks in advance

# Help needed regarding a Suffix Array Problem

Hi

Let R be the reverse of string S.

Letās build the suffix array SUF of S+R.

Let nextPos be the next position we have to fill in the resulting string (ANS).

Now letās loop over SUF.

For any index i (starting from 0) if SUF[i] >= |S| it means we are talking about a reversed prefix of S.

Otherwise we are talking about a suffix of S.

For the first case we have to check if the reversed prefix refers to characters we have already considered. If SUF[i] - |S| > |R| - 1 - nextPos we have to jump to the next i.

Otherwise, we have to put R[SUF[i] - |S|, |R| - 1 - nextPos] into ANS.

Instead, while SUF[i] refers to a suffix of S and SUF[i] = nextPos, we just have to put S[SUF[i]] into ANS. Is SUF[i] != nextPos jump to the next i.

In any case we have to decrease K by 1.

We stop when K = 0 or nextPos = |S|.

At the end if nextPos < |S| we have to choose to complete ANS with the last segment reversed or not. Just compare them.

This is my code:

https://www.hackerearth.com/submission/32117500/

Not sure if it is visible by others.

The suffix array implementation is not mine. It gives TIME OUT for some TC but i believe we could improve some implementation aspects.

However, the problem statement is not well written. It talks about āK consecutive substringsā but actually means āK split pointsā. Otherwise, with K = 1 the only 2 possible answers would be R or S itself.

Hi

If you are interested in yet, I have substituted the suffix array implementation with my version and got AC.

According to the site where I got it, the previous one was O(N(logN)^2) (where N is the length of the text).

This one is O(N).

Mine give TLE on two testcases as well. I have tried all optimiziations I could think of, but on my laptop those two take around 2 seconds.

Maybe gotta build suffix array in \mathcal O (N).