ЛКШ 2018, 7-й день, Строки-1 (Илья Подуременных)

  1. Бор
    1. Описание. Способы хранения. Array, list, map, hashMap, splay. Хеш-таблицу выгодно хранить одну большую.
    2. За сколько работает сортировка бором? O(∑i leni × log|Σ|), за линию нельзя, т.к. нельзя вообще.

  2. Алгоритм Ахо-Корасик
    1. Постановка задачи, решение бором в лоб за O(|text|*max|si|). Решение хеш-таблицей за то же время.
    2. Как оптимизировать решение бором? Аналогия с поиском подстроки в строке за O(nm) и префикс-функцией, определение суффссылок.
    3. Вычисление суфф ссылок. Порядок вычисления: bfs. Фиктивная вершина.
    4. Доказательство времени работы O(∑leni): для каждой строки суммарное время вычисления по всем символам строки O(leni).
    5. Тонкость оценки времени работы: не O(размера бора), а именно O(суммы длин строк)
    6. Полный автомат: вычисление next[v,char] для всех char, использование для получения суфф ссылок за O(1). Практика: ленивое вычисление.
    7. Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку; пример (s1=ababac, s2=bab : t=ababax).

  3. Суффиксный массив
    1. Напоминание, что суффмассив весит O(n) и мы его умеем строить хешами за O(nlog2n)
    2. Поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)
  4. Суффиксный массив за O(nlogn)
    1. Сортируем циклические сдвиги строки s#
    2. За O(Σ + n2) цифровой сортировкой
    3. От k переходим не к k+1, а к 2k, внутри используем сортировку подсчётом для пар, уже отсортированных по второй половине
    4. Учимся писать. Должно получиться что-то типа моего
    5. Касаи за O(n) для подсчёта LCP

  5. Задачи на суффмассив
    1. Число различных подстрок
    2. Поиск общей подстроки k строк
    3. LZSS (архиватор)
    4. Поиск подстроки в тексте за O(|s| + log|text|)
      1. Собственно алгоритм: SM ≥ max(min(SL, ML), min(SR, MR))
      2. Вычисление ML и MR за O(1) с предподсчётом за O(n): дерево отрезков
      3. Доказательство того, что при SM++ увеличится на следующей фазе max(SL, SR)

  6. Задачи на тему Ахо-Корасик (в конце, т.к. имеет меньший приоритет)
    1. Поиск подстроки в боре
    2. Посчитать для каждого словарного слова, сколько раз оно встречается в тексте, найти самое левое и самое правое вхождения
    3. Разбить строку длины 105 на словарные слова суммарной длины 105.