Тема: Суффиксный автомат
Такой вопрос, эта структура очень уж похожа на суффиксное дерево, даже я бы сказал это оно и есть для суффиксов. И я так понимаю это не алгоритм Укконена? Объясните пожалуйста, не понимаю.
Re: Суффиксный автомат
В нулевом приближении похожа, но на самом деле заметно другая. Хотя и не сказать чтобы совсем другая.
Обе хранят все суффиксы строки в виде путей в графе; однако если в дереве эти пути могут только разветвляться, то в автомате они могут соединяться обратно.
Алгоритм для построения автомата попроще, чем Укконен, особенно в мелочах реализации: хитрых моментов гораздо меньше. Зато многие классические задачи в терминах автоматов осознать сложнее, чем в терминах деревьев. Иногда даже проще сначала понять решение с помощью дерева, а потом понять, как его трансформировать для дерева.
В целом, эти две структуры данных во многих вещах функционально эквивалентны. По дереву можно довольно легко построить автомат; перейти от автомата к дереву, если не ошибаюсь, можно так: построить автомат для ревёрснутой строки, взять дерево, построенное из его суффиксных ссылок, и подвесить за начальное состояние - и получится суфф. дерево.
Re: Суффиксный автомат
Ясно, спасибо!
Да, дерево понятно, оно именно дерево 
Просто я увидел что задачи которые решает автомат схожи с задачами которые решает дерево, но не заметил такой сложности, тем более в конце строки не увидел символа "$" :-D Да и рёбра не сжимаются 
Нужно разобраться, интересно стало.
А не подскажешь где можно хорошо прочитать про суффиксное дерево, нам на сборах рассказывали бегло, так показалось так легко 
Но не успел я там понять, и вообщем теперь нужно будет читать самому.
Если подкинешь статейку с кодами если ещё и будет, то буду благодарен!
Re: Суффиксный автомат
Да, конечно, "несжатие" рёбер в автомате - тоже очень большое отличие.
Почитать? Лучше Гасфилда (http://e-maxx.ru/bookz/files/gusfield.djvu) не видел ничего. Ну и остальные книги в разделе "строки" на http://e-maxx.ru/bookz/ содержат полезную информацию. Впрочем, готовых кодов там не найдёшь; хороший код лучше брать готовым. Я вроде на сайте у себя не выкладывал; может, здесь тогда и выложу код с моей лекции прошлым летом (правда, код можно сказать не мой - был позаимствован у команды Саратов СУ3, в которой, скорее всего, он был написан Сергеем Назаровым; я честно пытался его переработать и улучшить - ни на грамм не получилось ).
Re: Суффиксный автомат
Вот тут можно скопипастить
http://acm.mipt.ru/twiki/bin/view/Algorithms/UkkonenCPP
Re: Суффиксный автомат
Спасибо