=(

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: =(

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