Finally I implemented effectively O(n) suffix tree!
Most understable McCreight algo and Shen(Шень) explanation.
Now ~ 10 big string problem in timus will be simple.
In 1590 enaught to find sum of length edges of the tree.




Edited by author 05.02.2008 13:48

I absolutely agree with you. Problem can be easily solved tith Suffix tree.
I used Ekkonen algo and got AC :-))

I used Suffix Automaton and got AC )

LOL

Why?
it is O(|S|) algorithm)

Edited by author 30.08.2009 03:58

It's wonderful =)

If your algorithm is fast, you can try to solve the same problem - 1706 =)

Thank for very interesting suggestion.
1706 was seems for me as absolutely separated and new problem.

Is it a joke?

Thank again. You are right and I am wrong.
I simply take solution from 1590(my suff_tree_implementation)
and got Ac  for 1706 with one submission.
Interesting that I forgotten all details but this fact
doesn’t inhibit using of subprogram.

Edited by author 06.09.2009 12:19

It's interesting to compare suffix tree and prefix function for these two problems. Suffix tree works faster on N1590, but much slower on N1706.

to my mind, the best algorithm for both 1590 and 1706 is hash. =)

For me all probabalistics algos are nonsense.
The are good for contests but how can we
imaginate them as basis of control in real life.
They have not scintists value!