Тема: Суффиксное дерево
Если не трудно - можете рассказать про него, зачем нужно, применение, построение ( ну за квадрат хотя бы, но если за O(n) - вообще класс ) а если еще и в разделе Algo будет - здорово))
Re: Суффиксное дерево
Посмотри статью "алгоритм Ахо-Корасик", там первая часть посвящена такой структуре данных, как строковый бор и её построению. Собственно, суффиксное дерево для строки s - это бор, построенный из всех её суффиксов. Поэтому построение за квадрат тривиально: нужно выполнить функцию add_string для всех суффиксов строки s.
Построение за O(n) (на самом деле применяемые на практике алгоритмы работают за O(n log k), где k - размер алфавита, есть только алгоритм Фарача с настоящим линейным временем, но он непрактичен) - это достаточно сложные алгоритмы (Мак-Крейта и Укконена), и я не разбирался с ними.
На самом деле, у суффиксных деревьев очень достойная конкуренция: суффиксные массивы, суффиксные автоматы, хэши наконец. На многих конкретных задачах эти альтернативные структуры данных также позволяют находить решение, а по сложности реализации все они, пожалуй, проще суффиксных деревьев. Мне за всю практику встречалась только одна задача (и то в специфических Петрозаводских контестах), для решения которой требовался настолько высокий уровень абстракции, что, по-видимому, кроме суффиксных деревьев та задача никак не "поднимается".
Примеры задач? Ну это в общем-то те же задачи, что приведены в моих статьях к "альтернативам":
поиск подстроки в строке: первое вхождение, все вхождения, количество вхождений
количество различных подстрок строки
наидлиннейшая общая подстрока двух и более строк
наименьший циклический сдвиг
Re: Суффиксное дерево
Как бы мощь суфф. деревьев в том, что они объединяют возможности других, более "лёгких" структур, да и уровень абстракции на них более высокий, поэтому решения многих задач в терминах суфф. деревьев получаются проще. Расплата за это - далеко не простой алгоритм построения дерева.
Re: Суффиксное дерево
Спасибо) Почитаю внимательнее Ахо-Корасика. Просто альтернативные структуры я вроде как разобрал и применяю, а вот тут как то не мог ничего толком найти)
Re: Суффиксное дерево
В смысле не смог найти задачи именно на дерево? Я могу попробовать вспомнить ту задачу с ПЗ 
Re: Суффиксное дерево
ну я помню на одном разбора Станкевич говорил, что суффиксное дерево помогло бы решить) Но там вроде у меня прошли хеши и Z функция. Поищи плз, буду благодарен)
Re: Суффиксное дерево
Вообще есть такое предположение, что суффиксное дерево и суффиксный автомат эквивалентны в плане множества задач, которые можно решить и тем, и другим (хотя, всё-таки, иногда бываю задачи, когда на суфф. дереве получается что-нибудь стандартное типа LCA, а на суфф. автомате - что-то жуткое получится ), не говоря уж про остальные "альтернативы" - та же z-функция при глубоком понимании оказывается весьма мощным инструментом.
Что же до той задачи - к сожалению, с зимних сборов прошло уже достаточно времени, чтобы я успел подзабыть её. Вроде бы задача такая: по данной строке длины 10^5 для каждой позиции i посчитать наибольшую длину B[ i], что две подстроки длины B[ i], начинающиеся в i и заканчивающиеся в i-1 соответственно, совпадают. Border-function это называется, если я не ошибаюсь. Задача эта, по-видимому, из этого контеста:
Andrew Stankevich Contest 34, Monday, February 2, 2009
хотя не уверен, это чисто по памяти.