Неточное совпадение

Задача: найти все позиции, где образец $p$ входит в текст $t$, если разрешено не совпасть в не более чем $k$ символах. Замены, без вставок и удалений.

При $k = 0$ это обычный поиск подстроки. При $k \ge 1$ префикс-функция перестаёт работать: она умеет только точные совпадения.

Случай одной ошибки

Окно $t[l..l+n)$ подходит, если несовпадение в нём не больше одного. Разобьём окно на три части: совпавший префикс, один плохой символ, совпавший суффикс.

Значит, нужны две величины:

• $\mathrm{pre}(l)$ - длина наибольшего общего префикса $p$ и $t[l..]$;
• $\mathrm{suf}(l)$ - длина наибольшего общего суффикса $p$ и $t[..l+n)$.

Условие: $\mathrm{pre}(l) + \mathrm{suf}(l) \ge n - 1$. Ровно одна позиция остаётся непокрытой - это и есть допустимая ошибка. Если $\mathrm{pre}(l) \ge n$, ошибок нет вовсе.

Обе величины - это z-функция склеек:

vector<int> zp = zFunction(p + '#' + t);                    // префиксы
vector<int> zs = zFunction(rev(p) + '#' + rev(t));          // суффиксы
for (int l = 0; l + n <= m; l++) {
    int pre = zp[n + 1 + l];
    int suf = zs[n + 1 + (m - (l + n))];
    if (pre + suf >= n - 1) answer.push_back(l);
}

Индекс во второй склейке стоит вывести на бумаге: окно кончается в позиции $l + n - 1$ строки $t$, а в перевёрнутой строке это позиция $m - (l + n)$.

Всё вместе - $O(n + m)$ времени и памяти.

Проверено: на 6000 парах коротких строк над алфавитами из 1-3 букв совпало с прямым подсчётом несовпадений в каждом окне.

Случай k ошибок

Тот же приём обобщается, но перестаёт быть линейным. Для окна $l$ прыгаем по нему:

позиция = 0, ошибок = 0
пока позиция < n и ошибок <= k:
    длина = наибольший общий префикс p[позиция..] и t[l+позиция..]
    позиция += длина + 1        // символ на стыке и есть ошибка
    ошибок += 1

Каждый прыжок стоит $O(1)$, если уметь спрашивать наибольший общий префикс двух суффиксов за константу. Прыжков не больше $k + 1$ на окно, итого $O(mk)$.

Приём известен как «метод кенгуру». Заметьте, чего он требует: наибольший общий префикс произвольных суффиксов, а не только суффикса и начала строки. Z-функция такого не даёт - нужны либо хеши с бинарным поиском, либо суффиксный массив с разреженной таблицей.

При $k = 1$ хватает двух z-функций именно потому, что прыжок ровно один и обе его половины упираются в края образца.

Чего этот приём не умеет

Только замены. Как только разрешены вставки и удаления, задача становится про редакционное расстояние, и линейного решения у неё нет.

Ещё одна ловушка формулировки: «не более одной ошибки» и «ровно одна ошибка» - разные задачи. Во второй из ответа надо выбросить точные вхождения.