ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1517. Свобода выбора

Suffix tree construction
Послано Giorgi Saghinadze (Tbilisi SU) 12 ноя 2007 15:55
How to construct suffix tree in N*log(N) time?
I am searching it in internet for 2 days and can't find site where all will be explained clearly.
If you now link where suffix tree constuction algorithm is explained clearly give me please.
thanks.
Re: Suffix tree construction
Послано Rafail Ahmadisheff 27 янв 2008 02:47
Actually, you'll find it possible to construct a Suffix Tree in O(N) (-: First such algo was offered by Weiner in 1973.
Some new ideas have sprung to life since then. I believe, nowadays Ukkonen's algorithm for online suffix tree construction is your best choice for most applications. http://en.wikipedia.org/wiki/Ukkonen's_algorithm
I personally tried a pair of its implementations:
1) Using explanation by Lloyd Allison ( http://www.allisons.org/ll/AlgDS/Tree/Suffix/ ) and implementation by Stephan T. Lavavej ( http://nuwen.net/libnuwen.html ) as base, I coined some C++ code... It got TLE 12.
2) Then I considered Dan Gusfield's book "Algorithms on Strings, Trees and Sequences" (Strictly speaking, I was reading Russian translation by Romanovsky - if it matters). And, you know, they made some sample programs in C available online ( http://www.cs.ucdavis.edu/~gusfield/strmat.html ) TLE 10 was the best judgement result I ever saw on this attempt.

I finally solved the problem with DAWGs (also known as Suffix Automata). This time I referred to "Automata for Matching Patterns" by Maxime Crochemore and Christophe Hancart for ideas, proofs and samples all along ( http://www-igm.univ-mlv.fr/~mac/REC/B4.html ). AC in 0.125 s.

Thus I got disappointed with Suffix Trees: despite them being good for theoretical considerations, in practice I'd rather be using Suffix Automata from now on.
Re: Suffix tree construction
Послано svr 6 фев 2008 17:42
In this problem there is a big another problem:
Create rather many triks to implement
suffix tree maximally compact, because
test were very optimized by authors.
For example such structure as vector is unsatisfactory for
description of adjast list in each node.
I were forced to organize dynamic memory allocation
by small parts for each new edge in int *smeg
with rewriting stored information.
Thank you! (-)
Послано Rafail Ahmadisheff 16 фев 2008 23:35