Строки: суффиксное дерево (11 ноября 2024)

1. Бор
   1. Способы хранения. Array, list, treeSet, hashSet, splaySet. Хеш-таблицу выгодно хранить одну большую.
   2. Сортировка бором за O(∑_i len_i × log|Σ|).
   
   
2. Алгоритм Ахо-Корасик
   1. Постановка задачи, решение бором в лоб за O(|text|*max|s_i|)
   2. Как оптимизировать? Связь с префикс-функцией, определение суффссылок.
   3. Вычисление суфф ссылок. Порядок вычисления: bfs. Фиктивная вершина.
   4. Доказательство времени работы O(∑len_i): для каждой строки суммарное время вычисления по всем символам строки O(len_i).
   5. Тонкость оценки времени работы: не O(размера бора), а именно O(суммы длин строк)
   6. Полный автомат: вычисление next[v,char], использование для получения суфф ссылок за O(1). Практика: ленивое вычисление.
   7. Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку (s₁=ababac, s₂=bab : t=ababax).

1. Суфф дерево
   1. Сжатый бор. Хранение: Edge next[v,c]; int p[v], pc[v]; или int next[v,c]; Edge p[v]; (информацию про ребро хранится в вершине, куда ведёт ребро)
   2. Суфф дерево за [T=O(n²), M=O(n)]. Пример: ababb.
   3. Задача "поиск подстроки в тексте" за O(|s|) суфф деревом. ∀ подстрока ⇔ путь от корня в суффдереве. ⇔ вершина суффдерева. Число вхождений.
   
   
2. Алгоритм Укконена построения суфф дерева в online
   1. Простая версия за [T=O(n²), M=O(n)]: храним указатели на концы суффиксов. Пример: ababbaa.
   2. Суффиксы-листья растут сами. Два варианта реализации: наростить сразу до конца, или хранить ребро [l,&inf;]
   3. Жизненный цикл суффикса (1) идёт по дереву, (2) разветвился, (3) саморастущий лист.
   4. Основная лемма: если суффикс не разветвился, то все более короткие тоже не разветвились.
   5. Алгоритм: храним указатель на самый длинный не разветвившийся, пересчитываем его.
   6. Суффссылки. Лемма: суффиксная ссылка вершины − вершина
   7. Подсчёт суфф ссылки. Линейность времени работы.
   8. Пример построения на строке "ababbaabbc".
   9. Псевдокод.
   
   
3. Тонкости реализации
   1. Фиктивная вершина помогает два раза: всегда есть суфф ссылка, всегда будет (1)-суффикс
   2. При создании новой суфф ссылки, может оказаться, вершина ещё не создана... но мы уже знаем её номер (наша нумерация − автоинкремент).
   3. После перехода по суфф ссылке идти вниз нужно, пока не дойдём до вершины, до которой "чуть-чуть не достаём".

1. Бонус. Задача: пусть даны два корневых дерева, проврить их на изоморфизм
   1. nlogn : динамика, хеш от сортированного массива детей
   2. n : динамика, умные хеши от множеств
   3. n : динамика, но сортрировка детей → перебираем типы детей по возрастанию
   4. n : хеш-таблица от хеша от вектора → бор от вектора в число
   5. но в каждой вершине бора нужно хранить только последнее ребро...