Лекция 7. Приближённый поиск подстроки

Задача поиска образца с джокерами. Поиск образца с '?'. Деление шаблона на куски без джокеров. Поиск всех вхождений всех кусков алгоритмом Ахо-Корасик. Вычисление массива счётчиков: кол-во совпавших кусков при прикладывании образца к данному месту. Время работы 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)).