Добрый вечер.

Нужно найти образцы в заранее неизвестном тексте, ну то есть сначала подаются на вход образцы, потом только текст, то есть нужен гуд препроцессинг, чтобы потом поиск можно было осуществить за линейное время, напрашивается Ахо-Корасик, но по заданию надо делать именно через суффиксные деревья.

Я в замешательстве.. Суфф. деревья обычно применяют, когда нужно решить обратную задачу (поиск в тексте неизвестных  образцов, то есть препроцессинг осуществялется именно текста, что логично).

Нашел что-то по теме только в Гасфилде, но там буквально пару слов, мол, да, применяют иногда, так как можно выиграть по времени\памяти Ахо-Корасик в некоторых случаях, но КАК это сделать ничерта не написано   

Помогите пожалуйста, как это делается?

Заранее благодарен.

Задание действительно странное, потому что Ахо-Корасик как раз хранит информацию только о всех образцах, в то время как суффиксное дерево будет хранить информацию и обо всех их суффиксах (что теоретически позволяет искать вхождения не только образцов, а подстрок образцов, но в задаче-то этого не надо).

Т.е., рассуждая так, суффиксное дерево содержит в себе всё то, что "знает" Ахо-Корасик, а, значит, и задачу можно решать аналогично. Построим суфф. дерево для строки "s1 # s2 @ s3 & s4 ...", где #@& - это различные символы, позволяющие отделять каждый образец от остальных (т.е. образцы конкатенируются через эти символы). "Скармливая" такому дереву текст, мы будем совершать переходы по дереву аналогично алгоритму Ахо-Корасик: по возможности переходя по ребру с нужным символом, если такого ребра нет - переходя по суффиксной ссылке. Если пришли в состояние, соответствующее одному из образцов, то значит вот нашли очередное вхождение.

Спасибо, была такая идея, но, думал, может что-то более изящное есть.

Остался только вопрос:
Есть идея как генерить уникальные символы? В задаче используется латинский алфавит, значит все остальные подойдут, но образцов может быть и миллион, как же тогда нагенерить их столько?

Ну то, что в исходных строках только буквы латинского алфавита, никак не мешает тому, чтобы алфавит имел размер миллион  При программировании это будет означать, что для представления символа будет использоваться не однобайтовый тип, а обычный целочисленный.

(Вообще говоря, для суффиксного дерева размер алфавита может быть практически любым, т.к. размер дерева является величиной O(N) независимо от алфавита, а асимптотика алгоритма Укконена - O(N * log Alphabet).)

Немного не это имел ввиду.. Мой вопрос гораздо более глупый, чем показалось.
Имелось ввиду, как получать эти символы, а затем сопоставлять с номером образца, ведь нужно при встрече терминального символа в дерере сказать, какой именно образец мы встретили.
Я так понимаю, нужно использовать интовый массив вместо чаров и брать символы по порядку начиная с определенного, например сразу после маленькой z и тогда номер образзца получать обычным вычитанием..

Ну да, конечно, как-нибудь так: буквы 'a'-'z' это "нормальные буквы", а дальше идут "псевдо-буквы" для первого, второго, третьего и т.д. образцов.

А теперь вопрос по самому алгоритму, вообще их 2:
1) Какую роль Вы отводите суффиксным связям, я так и не понял, при переходе по суффиксной связи мы получаем абсолютно те же дочерние дуги, лишь отрезая первый символ, но это нас не особо волнует, он где-то вверху, что же это может изменить? В общем, зачем?
2) Как быть, если прикладывая текст к дереву мы нашли терминальный символ, по идее вхождение, но это может быть суффиксом образца, а не им самим, как же это проверить?

Так что я так ничего и не понял, как правильно искать обрацы, можно уточнить?