| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Суффиксное дерево |
| Автор: Skalik 17.10.2008, 23:32 |
| Подскажите алгоритм построения и обхода суффиксного дерева. |
| Автор: maxdiver 4.12.2008, 09:33 |
| Странно, что никто так и не ответил. Можно легко построить суффиксное дерево за N^2, алгоритм тогда превращается в построение бора. Если нужно за строить за линейное время, то тогда алгоритмы Укконена или Мак-Крейта. Хорошо написано, на мой взгляд, об этих алгоритмах в Гасфилде. Есть ещё алгоритм такой: строим суффиксный автомат для реверснутой строки, а потом из него получаем суффиксное дерево как дерево, составленное из обращённых суффиксных ссылок. Возможно, по коду это получится самый простой алгоритм, хотя я не пытался его реализовать. |