ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1713. Key Substrings

=(
Posted by Dima Kravtsov 11 Oct 2009 21:45
Please, give me some hints on how to solve it. Thanks in advance.
Re: =(
Posted by Vedernikoff Sergey (HSE: АОП) 12 Oct 2009 23:35
Hash rulezz =)
Re: =(
Posted by Igor9669(Tashkent IAC) 12 Oct 2009 23:57
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: =(
Posted by Victor Barinov (TNU) 13 Oct 2009 15:47
Try use hash table to avoid logN
Re: =(
Posted by Vedernikoff Sergey (HSE: АОП) 14 Oct 2009 16:55
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: =(
Posted by Igor9669(Tashkent IAC) 16 Oct 2009 12:41
Thanks to all!!!
Re: =(
Posted by Petr Nikishin 5 Apr 2010 07:58
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 xurshid_n 15 Jan 2012 23:01
Petr Nikishin wrote 5 April 2010 07:58
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: =(
Posted by Mahilewets 11 Jul 2017 16:21
(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: =(
Posted by Mahilewets 11 Jul 2017 18:06
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