### sajalhsn13's blog

By sajalhsn13, history, 5 years ago,

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.

• +9

| Write comment?
 » 5 years ago, # |   +35 You should also try solving with the algorithm. Its constant is very good in comparison with the O(n) one, and it may pass.
•  » » 5 years ago, # ^ |   +3 Time limit is 0.236s. :(
•  » » » 5 years ago, # ^ |   +30 O(nlogn) isn't hard to write and the only difference is that it uses radix sort instead of an O(nlogn) sort
•  » » » » 5 years ago, # ^ |   0 Does using radix sort give a considerable boost or is it only just slightly beneficial ?
•  » » 5 years ago, # ^ |   0 You might have solved quite a few problems involving suffix arrays. By the looks of it an O(n lg2 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 lg2 n) suffices?
•  » » » 5 years ago, # ^ |   +3 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.
•  » » » » 5 years ago, # ^ |   +16 O(nlogn) is already slightly faster than O(nlog^2n) at n=10^5.O(nlogn):http://mirror.codeforces.com/contest/1037/submission/42866304http://mirror.codeforces.com/contest/1037/submission/42964984http://mirror.codeforces.com/contest/1037/submission/42965008O(nlog^2n)http://mirror.codeforces.com/contest/1037/submission/42964934http://mirror.codeforces.com/contest/1037/submission/42964987http://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)
•  » » » » » 5 years ago, # ^ |   0 Thanks :)
•  » » » » 5 years ago, # ^ |   0 Thanks :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 TLE with O(nlogn). Radix sort does not helps here. code: https://paste.ubuntu.com/p/NCbb3HynX3/
•  » » » 5 years ago, # ^ |   0 Try using faster i/o, like scanf/printf.
 » 5 years ago, # |   +32 No, you don't need suffix array. Try to learn easier techniques
•  » » 5 years ago, # ^ |   +3 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.
•  » » 5 years ago, # ^ |   0 Which easier techniques can be useful? I need hints.
•  » » » 5 years ago, # ^ |   +5 SpoilerBinary search on size of substring, then hashing (rolling hash or prefix hashing works well)
•  » » » » 5 years ago, # ^ |   0 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?
•  » » » » » 5 years ago, # ^ |   +8 Not better complexity, better constant factor.