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 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?
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.
Binary 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.