|
|
вернуться в форумPlease, give me some hints on how to solve it. Thanks in advance. Hash rulezz =) 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 Try use hash table to avoid logN 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 (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 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 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 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! |
|
|
