About the solving approach(+)
Послано
SPIRiT 29 окт 2007 21:43
I know that suffix trees can be used for such problem. How about using a large hash table for storing codes of substrings that we already have? Anyone got AC in that way?
Re: About the solving approach(+)
Послано
svr 29 окт 2007 22:16
I trying during a long time O(n) suffix tree of Ekkonen
but could'n catch all details. I think that you
question has the same nature. If you think about
yourself as good coder you should catch O(n) suffix tree.
Re: About the solving approach(+)
I tried double-hash of about 30000 elements each but WA. Nevertheless, some people claim the problem may be solved with hash.
Re: About the solving approach(+)
Послано
Lomir 13 ноя 2007 04:25
How do you calculate hash for n^2 substrings?
I calculate hash seperately for each lenth os substring by:
hashcode = prime^n*c1 + prime^(n-1)*c2 + prime^(n-2)*c1...
string movement is by 1 char:
newhashcode = (oldhashcode - prime^n*removedchar)*prime + prime*addedchar
This gets TLE 3.
Re: About the solving approach(+)
I use 'poganyi hash'. And it works very good. Yeah, baby!
Re: About the solving approach(+)
Послано
SPIRiT 6 авг 2009 00:46
Finally managed to implement the Ukkonen algo correctly - worked from the first try and is much faster now, than with O(N^2) implementation. Here is my status board to examine:
http://acm.timus.ru/status.aspx?space=1&num=1590&author=33910 Edited by author 06.08.2009 00:47 Edited by author 06.08.2009 00:48Re: About the solving approach(+)
to Lomir: you should not use sorting. Without sorting this approach gives AC in 0.454 sec.
Re: About the solving approach(+)
Calculation of hash for each substring will take O(N^2). Then you need to check non-equal of string with same hash. For example for test 'aaaaaaaaaaaaa' (and longer) every substring of same length will have same hash code
Re: About the solving approach(+)
Can it be done using ternary search tree