Ukkonen's algorithm question

Revision en3, by Infoshoc, 2017-10-12 15:03:49

Hello,

I had to learn Ukkonen's algorithm in order to solve this question. So I searched something found this, and this, and this, and this. Decided that I understood theory and could proceed to implementation of this problem.

I tried to implement it readably and reliable and tested it a bit and received TL afterwards optimized and got TL with this, so I rewrote code and still got TL and my vacation run to an end.

Can you please help me and tell what am I missing (seems like major difference from e-maxx's implementation is that I am calculating suffix links not on the fly but when coming to next vertex (it is suffix link of previous)

Thank you and kiitos

Tags ukkonen, suffix tree, implementation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Infoshoc 2017-10-12 17:28:49 1150 Первая редакция перевода на Русский
en3 English Infoshoc 2017-10-12 15:03:49 9 Tiny change: 'Helo,\n\nI h' -> 'Hello,\n\nI h'
en2 English Infoshoc 2017-10-12 09:19:44 13 Tiny change: 'nce from [[user:e-maxx]'s implementa' -> 'nce from [user:e-maxx]'s [implementa'
en1 English Infoshoc 2017-10-12 09:19:13 1210 Initial revision (published)