Строки: основные понятия и обозначения (алфавит, строки, подстроки, суффиксы, префиксы, лексикографический порядок). Задача поиска образца P в тексте T. Longest Common Prefix, Z-функция. Точный поиск подстроки через Z-функцию от P#T. sentinel-символ.

Алгоритм вычисления Z-функции за линейное время. Поиск через Z-функцию с O(P) дополнительной памяти, отделение предподсчёта от поиска. Расстояние редактирования ED. Неточный поиск подстроки (ED <= 1). Реализация поиска через Z-функции от P#T и rev(P)#rev(T). Использование Z-функции для вычисления LCP вида LCP(A, suffix(B)) за O(1).

Алгоритм Кнута-Морриса-Пратта: идея, время работы. Префикс-суффиксы (borders), максимальный из них, множество всех префикс-суффиксов строки. Префикс-функция строки. Алгоритм вычисления префикс-функции, время работы. Префикс-функция строки P#T, предподсчёт и поиск КМП. Много образцов: время работы. Бор (trie), вставка слов в бор. Порождённый образцами бор, пометки вершин бора. Определение функции отката FF(a). Проход по тексту с отслеживанием вершины в боре, время работы. Определение найденных вхождений образцов, время работы. Построение функции FF, порядок обхода вершин (в ширину), время работы. Зависимость затрат времени и памяти от размера алфавита: использование массива, списка, дерева поиска для хранения переходов.

Поиск образца: один текст и много образцов (online). Суффиксный бор. Поиск вхождений образца на суффиксном боре. Размер бора O(T^2). Сжатие цепочек в боре → суффиксное дерево размера O (T). Алгоритм Укконена. Положения в дереве: явные и неявные. Строим дерево, добавляя по одному символу или итерации слева направо.

Удлиняем суффиксы в дереве (шаги) в пор-ке уменьшения длины. Три типа шагов. O (T) шагов второго типа — ветвлений. Шаги третьего типа или проходы делать не нужно. Бесплатное выполнение шагов первого типа — листьев. Все продолжения вершины AB являются продолжениями вершины B. Упорядоченность типов шагов на итерации. Старт итерации: в том месте, где на пред. итерации был первый шаг третьего типа. Суффиксная ссылка.

Вычисление суффиксной ссылки от неявного положения, случай с корнем. Анализ времени работы. Путь алгоритма, его длина O (T). Вершинная глубина. Связь изменения вершинной глубины и времени вычисления суффиксной ссылки. Суммарное время вычисления суффиксных ссылок O (T).

LCP-структура. Суффиксное дерево для S = A$B#. Сведение LCP суффиксов A и B к LCA вершин суффиксного дерева S. Суффиксный массив (SA). Определение, обратный суфф. масс. (ISA). Две нумерации суффиксов: по позиции в строке, по рангу в суфф. массиве. Поиск образца при помощи SA. Бинарный поиск за O(P log T). Хранение LCP с образцом на границах отрезка. Использование LCP среднего и граничных суффиксов. Почти полное определение топологии бора с левым, правым, средним суффиксом и образцом, посимвольное сравнение в проблемном случае. Время работы O(P + log T). Построение SA. Добавление sentinel-ов после конца строки. Разметка (labelling) множества строк в порядке сортировки. Идея: строим разметку phi_k для всех подстрок длины 2^k, k = 0..logN. Начальная разметка phi_0 - сортировка подсчётом. Переход от разметки phi_k к разметке phi_{k+1} - цифровая сортировка пар рангов. Время работы O(N log N + C). Сохранение разметок phi_k в построении SA (всего O(N log N) памяти). Вычисление LCP двух суффиксов за O(log N) с их помощью.

Построение SA для строки S за O(N + C), алгоритм Kaerkainen-Sanders. Суперсимволы (тройки), формирование и нумерация супералфавита. Строка T из суперсимволов длины 2/3 * N и рекурсивный вызов SA. Классы суффиксов S по остатку от деления начальной позиции на 3: =0, =1, =2. Соответствие суффиксов T и суффиксов S классов =0 и =1. Возможность сравнения суффиксов классов =0 и =1 между собой за O(1). Сравнение суффиксов из класса =2 с остальными за O(1). Порядок суффиксов классов =0 и =1 (по SA строки T). Определение порядка классов =2 (radix sort). Слияние порядков за линейное время. Время работы O(N). LCP-структура. Определение lcp-массива. Сведение LCP двух суффиксов к RMQ на lcp-массиве. Оптимальное решение (O(N) времени на предподсчёт, O(1) времени на запрос). Вычисление lcp-массива. Порядок: ISA[p] для 1..n. Свойство: lcp[ISA[p+1]] >= lcp[ISA[p]] - 1. Простой алгоритм за O(N)

Определение матрицы BWT, строки BWT. Построение BWT(S) за O(N) через SA(SS). Восстановление матрицы по строке BWT (много radix-sort). обращение BWT с точностью до цикл. сдвига. Алгоритм обращения за O(N). Перестановка shl на строках матрицы при циклическом сдвиге влево, её предподсчёт за O(N). Добавление sentinel-а для однозначного обращения BWT. Поиск образца за O(P). Отрезок строк матрицы [l;r]. Добавление к образцу символа слева и изменение отрезка. Сведение к операции rank на строке BWT. Сведение перестановки shl к операции select. Задача rank/select для строки (запросы только rank). Случай бинарного алфавита: префиксные суммы, префиксные суммы для машинных слов, алгоритм RRR (O(N log log N / log N) бит памяти, O(1) времени). Сведение случая произвольного алфавита к бинарному алфавиту (O(log C) времени, суммарная длина N log C бит). Определение позиции в исходной строке по строке в матрице. Решение с O(N/K) слов памяти, O(K) времени.

Задача поиска образца с джокерами. Поиск образца с '?'. Деление шаблона на куски без джокеров. Поиск всех вхождений всех кусков алгоритмом Ахо-Корасик. Вычисление массива счётчиков: кол-во совпавших кусков при прикладывании образца к данному месту. Время работы O(P + T + A), память O(P + T). Сокращение расходов памяти до O(P). Количество символов, совпавших при прикладывании к позиции. Фильтрация по каждому символу. Скалярное произведение векторов при движении одного относительно другого. Сведение к свёртке. Применение FFT. Решение за O[C (P+T) log (P+T)]. Бинаризация алфавита, решение за O[ (P+T) log C log ( (P+T) log C) ]. Локальность, разбиение текста на блоки длины 2|P|. Решение за O[ (P+T) log C log (P log C) ]. Расстояние редактирования (ED). Задача поиска подстроки в тексте с расстоянием до образца <= k. Предположение о наличии LCP-структуры (оптимальной). Вычисление ED(a, b) за O(a b). Графовое представление задачи. Модификация для подстроки: бесплатные добавления в начало/конец; пути в подпрямоугольниках. Решение задачи прибл. поиска за O(P T). Оптимизация: D[t] - множество вершин на расстоянии <= t. Итерационный алгоритм. Граница D[t]. Итерационный алгоритм вычисления границ. База: граница D[0]. Спуск по диагонали за O(1). Шаг: построение границы D[i+1] по границе D[i]. Корректность. Время работы O(k (P + T)).

Ориентированные графы. Задача о достижимом множестве. Представления графа. Список рёбер, матрица, списки исходящих/входящих. Память и время работы общих операций для этих структур. Статический граф: плотно упакованные списки исходящих. Обход в ширину (BFS). Случай единичных весов. Слои вершин по расстоянию, рекуррентное соотношение. Построение слоёв один за другим. Хранение двух соседних слоёв в очереди. Время работы O(V + E).

Обход в глубину, пометки вершин (NONE/IN/OUT). Классификация вершин по пометкам в процессе обхода. Отсутствие OUT->NONE рёбер, лемма о NONE-пути, док-во корректности алгоритма. Время работы O(V+E). Обход части графа за её размер.

Топологическая сортировка: определение, необходимость отсутствия циклов. Добавление фиктивной вершины, серия DFS. Определение цикла по ребру IN->IN. Время входа(tin) и выхода(tout) для вершины. Порядок топ. сорт. = порядок убывания tout. Доказательство. Сильная связность, компоненты сильной связности. Конденсация графа, сохранение достижимости, ацикличность. Поиск компонент сильной связности: прямой DFS + обратный DFS. Лемма о соотношении времён выхода двух компонент с ребром. Доказательство корректности алгоритма.

Эйлеров цикл (ор. граф). Критерий существования: слабая связность и равенство степеней входа/выхода. Док-во сильной связности. DFS по рёбрам, пометки рёбер, код. Список рёбер в порядке выхода - развёрнутый эйлеров цикл. Время работы O(V + E). Доказательство: первый возврат в стартовой вершине; в момент выписывания ребра сохраняется связность пути; обход затрагивает все вершины и рёбра графа.

Обход в глубину в неориентированном графе. Ориентация рёбер (при первом просмотре). Деление рёбер на корневые и обратные. Дерево обхода. Отсутствие прямых и перекрёстных рёбер. Двусвязность, мосты и точки сочленения. Критерий точки сочленения: для корня дерева, в общем случае (на основе обратных рёбер из поддерева сына). Функция верхнего: самый верхний конец обратных рёбер из поддерева. Способы сравнения вершин: по высоте, по времени входа. Рекуррентное соотношение для функции верхнего.

Функция длины пути, аддитивная функция, веса рёбер. Цикл отрицательного веса: проблема и различные варианты постановки задачи. Кратчайший путь простой, все подпути кратчайшие. Классы алгоритмов: point-to-point, SSSP, APSP. Общая идея: поддерживаем (реализуемые) оценки сверху на длины, операция релаксации. Алгоритм Форда-Беллмана. Псевдокод. Доказательство, поведение с циклом отр. веса. Время работы O(V E). Альтернативный вывод алгоритма: динам. прогр. вперёд, R[k, v] - кратч. путь от s до v из <=k рёбер, переходы. Слияние ответов для разных k воедино. Алгоритм Флойда. Оценки d[i,j], (i,k,j)-релаксация, псевдокод. Время работы O(V^3). Доказательство: динам. прогр. назад, R[k, i, j] - кратч. путь из i в j с промеж. вершинами <=k. Рекуррентное соотношение. Слияние ответов для разных k. Поведение с циклом отр. веса.

Алгоритм Дейкстры. Аксиоматика длины путей, примеры: аддитивная (неотр. веса), максимум. Пометки (W/G/B) вершин, их смысл. Инициализация. Идея: перекрашиваем серую вершину с мин. оценкой в чёрный. Просмотр вершины (функция Scan). Псевдокод алгоритма. Доказательство: обоснование перекрашивания G->B от противного. Время работы (аддитивная функция длины): O(V^2). Хранение серых вершин в куче. Бинарная куча O(E log V), k-ичная куча O(E log V / log(E/V)), фиббоначиева куча O(E + V log V). Восстановление пути, сохранение предка, дерево кратчайших путей.

Point-to-point алгоритмы. Ранняя остановка алгоритма Дейкстры. Двунаправленный алгоритм Дейкстры. Алгоритм A*. Алгоритм Дейкстры с потенциалами. Выбор phi(v) = dist(s, v), -dist(v, t) и пути по нулевым дугам. Использование оценки s(v) = dist(v, t). Условие допустимости оценок - неравенство треугольника, оценка снизу. Пример: евклидово расстояние для плоского графа. Алгоритм A* как алгоритм Дейкстры на исходном графе с правилом выбора вершины d(v) + s(v) = min. Алгоритм ALT. Множество вершин-маяков. Путь из s в t: две оценки снизу расстояния до t. Объединение по всем маякам, запуск алгоритма A*. Оценка трудоёмкости O(L E log V). Метод Highway Hierarchy. Разбиение графа на области, рёбра между областями, граничные вершины. При поиске неконцевые области заменяются на полные графы, предподсчёт расстояний между граничными вершинами. Алгоритм Джонсона. Задача APSP, есть отрицательные веса. Потенциалы вершин и потенциальное преобразование графа. Изменение веса пути и цикла. Сохранение кратчайших путей. Допустимые потенциалы: приведённые веса неотрицательны. Если есть цикл отр. веса, то допустимых потенциалов нет. Использование d(s, v) в качестве допустимых потенциалов. Алгоритм: Форд-Беллман + алгоритм Дейкстры (|V| раз). Время работы O(V * Dijkstra).

Определения: сеть, поток, задача о макс. потоке; разрез: поток и проп. способность; остаточная сеть, дополняющий путь. Теорема Форда-Фалкерсона. Метод Форда-Фалкерсона, реализация за O(F E). Поиск мин. разреза через поток. Проблемы мет. Ф.-Ф.: большое F в малом графе, зависание в вещественном случае. Алгоритм Эдмонса-Карпа: проталкивание вдоль кратчайшего пути (BFS). Лемма о неубывании расстояний, оценка количества насыщений, общее время O(V E^2). Алгоритм масштабирования Габова. Лемма: после delta-фазы остаётся менее (delta |E|) потока. Общее время O(E^2 log C). Метод Диница: сеть кратчайших путей и слои, блокирующий поток. Не более O(V) фаз. Поиск блокирующего потока за O(V E) с удалением рёбер, общее время работы O(V^2 E).