Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

You should also try solving with the algorithm. Its constant is very good in comparison with the

O(n) one, and it may pass.Time limit is 0.236s. :(

O(nlogn) isn't hard to write and the only difference is that it uses radix sort instead of an O(nlogn) sort

Does using radix sort give a considerable boost or is it only just slightly beneficial ?

You might have solved quite a few problems involving suffix arrays. By the looks of it an O(n lg

^{2}n) algorithm does not look like a good one that it can be used in almost any problem involving suffix arrays. So, in practice do you use any other implementation like the O(n) one or the O(n lg n) one to solve problems or the O(n lg^{2}n) suffices?You usually have to work very hard to make a radix sort faster than std::sort, since it's highly optimized. I never got the one to work faster than the .

As for the linear time one, the only thing I know about it is that it has a pretty large constant.

O(nlogn) is already slightly faster than O(nlog^2n) at n=10^5.

O(nlogn):

http://mirror.codeforces.com/contest/1037/submission/42866304

http://mirror.codeforces.com/contest/1037/submission/42964984

http://mirror.codeforces.com/contest/1037/submission/42965008

O(nlog^2n)

http://mirror.codeforces.com/contest/1037/submission/42964934

http://mirror.codeforces.com/contest/1037/submission/42964987

http://mirror.codeforces.com/contest/1037/submission/42965010

(I know this is not the best way to benchmark but I'm too lazy to do a proper one)

Thanks :)

Thanks :)

TLE with O(nlogn). Radix sort does not helps here. code: https://paste.ubuntu.com/p/NCbb3HynX3/

Try using faster i/o, like scanf/printf.

No, you don't need suffix array. Try to learn easier techniques

actually I have learnt the O(n*long*long) suffix array algorithm 3 or 4 days ago and found some problems in spoj which can be solved with suffix array. Those may be solved with other ways. But I am trying to practice suffix array and thats why I want to solve it with this algorithm.

Which easier techniques can be useful? I need hints.

SpoilerBinary search on size of substring, then hashing (rolling hash or prefix hashing works well)

I used suffix array with radix sort which time complexity is O(nlogn). If hashing + binary search is used how it will give better complexity?

Not better complexity, better constant factor.