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?

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.

I tried double-hash of about 30000 elements each but WA. Nevertheless, some people claim the problem may be solved with hash.

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.

I use 'poganyi hash'. And it works very good. Yeah, baby!

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:48

to Lomir: you should not use sorting. Without sorting this approach gives AC in 0.454 sec.

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

Can it be done using ternary search tree