|
|
back to board=( Posted by 1234321 11 Oct 2009 21:45 Please, give me some hints on how to solve it. Thanks in advance. Re: =( I also use hash,but TLE 3 =(
My complexity is O(N*MaxLen^2*logN).
What is your?
Edited by author 13.10.2009 00:06 Re: =( Try use hash table to avoid logN Re: =( My complexity is O(N^2*M^2*(logN+logM)), where M is maximal length of a word. It passes TL due to small constant.
P.S. You don't need hash tables to avoid N. Just one linear hash and sorting.
Edited by author 14.10.2009 20:41 Re: =( This problem can be very simply solved using standard techniques of suffix array + lcp array. Complexity is O(N * M * logN), M - length of the longest string. Due to all-round using of STL my solution works in 0.25, but this time can be hugely improved.
SkorKNURE
Edited by author 05.04.2010 08:00 Re: =( Posted by coder 15 Jan 2012 23:01 This problem can be very simply solved using standard techniques of suffix array + lcp array. Complexity is O(N * M * logN), M - length of the longest string. Due to all-round using of STL my solution works in 0.25, but this time can be hugely improved.
SkorKNURE
Edited by author 05.04.2010 08:00 You are right! I Ac! 0.046 s. Thanks! Re: =( (N^2)*(M^2)*(logN+logM)?
When N=1e3 and M=1e2?
Accepted?
Anybody knows how it was done?
Edited by author 11.07.2017 16:23 Re: =( So, I understood
If explicitly sort suffixes of string command1+command command2+command3+... we have upper bound N^2*M^2 but actual number of comparisons is smaller |
|
|
