Суффиксный автомат! пара нубо вопросов -_-

[Ksardas13]

Итак, я снова здесь.
Как обычно - мне нужно не решение, мне нужен толчок(нецензурное направление не предлагать)).

Есть некоторое кол-во строк и среди них нужно найти длиннющую общую подстроку. =3 Мне нужно направление, в какую сторону копать, ибо сроки сжаты - суффиксальные деревья, суффиксальные массивы или ещё какие техники, позволяющие разработать оптимальный алгоритм? Всего перечисленного(и даже больше) - я не знаю, так что сижу грызу.
Буду рад ответу-наводке. Если кто случайно знает крутую ссылку, которая мне поможет - тоже буду рад.))

PS: кстати, админы, у моего второго аккаунта(долгая история) Karp_13 внезапно сократилась функциональность - ни данные о себе посмотреть, ни тему создать. = ( В чем может быть проблема?

А, да, и ещё нубо вопрос - суффиксный автомат и суффиксное дерево - одно и тоже?
*ну щас пока погрызу, разберусь... но если дадите ответ раньше, буду рад))

[waleri]

Хорошее начало:
http://en.wikipedia.org/wiki/Longest...string_problem

[Ksardas13]

Хех, а ведь я даж не догадался посмотреть на английскую часть викии.) Вроде выглядит привлекательно(русская статья меня там чёт загрузила, я убежал искать что по практичнее есть)).
Чтож, спс, почитаю. Но пока нашёл http://e-maxx.ru/algo/suffix_automata (вдруг кому поможет, кто столкнулся с той же проблемой))). Сижу грызу. Вроде там есть то, что мне надо.))

[Ksardas13]

Эм, народ, а нет ни у кого программки, которая бы строила суффиксный автомат из любой введённой строки и наглядно показывало как он выглядит?
*да я знаю что можно самому написать... но может у кого готовая есть в целях экономии времени... просто сижу с кашей в голове пока... помог бы такой инструментик сильно*

[Ksardas13]

ВСЕГО ОДИН ДОП ГЛУПЫЙ ВОПРОС:
Если после построения суффиксного дерева в его конструкции остались лишние явные вершины(т.е. явные вершины с одним потомком и одни родителем; вершины которые не стоит делать явными и можно удалить, но они остались) - это плохо? Или так и должно быть?
*пока грызу алгоритм дальше, ищу ответ на свой вопрос... но коль поможете - буду очень благодарен
хотя лан, не суть, щас сам разберусь где накосячил)) тему можно в принципе удалить

[Darkwinged]

Тоже сейчас разбираюсь с алгоритмом http://e-maxx.ru/algo/suffix_automata#27
Пытаюсь вникнуть уже два дня, но никак не получается.
Если кто разбирается в этом, может набросать схему ссылок для строки вроде "so1go2"?
На сколько я понял, при каждом новом символе создаётся ответвление от начального состояния, но никак не могу понять по какому принципу объединяются состояния, и почему всегда есть ветка, которая не объединяется.
И также непонятно с терминальными состояниями. По определению это такие, проходя по любому пути к которым получается суффикс строки.
Но почему тогда в строке 'aba' первый переход по 'а' - является терминальным, а в строке 'аbb' - нет, ведь если перейти по 'а', то выписывается 'а' - и он является суффиксом?