Конспект: наивный поиск, Рабин-Карп, КМП

Понятия

Текст и образец - где ищут (длина n) и что ищут (длина m). Вхождение - позиция, с которой образец читается в тексте целиком. Вхождения могут перекрываться.

Алфавит - набор символов, из которых составлены строки. Чем он меньше, тем дольше образец совпадает со случайным текстом.

Полиномиальный хеш - строка как число по основанию x, взятое по модулю q. Ложное срабатывание - хеши совпали, строки разные.

Грань - начало строки, которое одновременно её конец и короче её самой.

Префикс-функция - π[i] равно длине самой длинной грани куска p[0..i].

Z-функция - z[i] равно числу символов, на которое кусок строки с позиции i совпадает с её началом. Z-блок [l, r) - самое правое из найденных совпадений с началом.

Что унести

ЧТО ПОМНИТ АЛГОРИТМ МЕЖДУ СДВИГАМИ          ХУДШИЙ СЛУЧАЙ       НА ОБЫЧНОМ ТЕКСТЕ
наивный       ничего                         (n − m + 1) · m     около n · k/(k − 1)
Рабин-Карп    хеш окна                       n · m               около n + m
КМП           сколько символов совпало       2n + подготовка m   около n
Z-функция     самое правое совпадение        2(n + m)            около n + m

Квадрат у наивного поиска - свойство данных, а не длины. На случайном тексте из k букв выходит k / (k − 1) сравнений на позицию: 2 при двух буквах, 1,04 при двадцати шести.

РАБИН-КАРП: пересчёт хеша при сдвиге окна
h = ((h − код_ушедшего · x^(m−1)) · x + код_пришедшего) mod q

хеши разные   → вхождения ТОЧНО нет
хеши равны    → вхождение ВОЗМОЖНО, сравнить посимвольно
ложных срабатываний около n / q:   q = 13 → 765,   q = 1009 → 9,   q = 1 000 003 → 0   (n = 10 000)

КМП: один шаг на символ текста c
пока k > 0 и c ≠ p[k]:   k = π[k − 1]        откат по образцу, текст на месте
если c = p[k]:           k = k + 1
если k = m:              вхождение;  k = π[m − 1]

индекс    0  1  2  3  4  5  6  7  8  9  10
образец   a  b  r  a  c  a  d  a  b  r  a
π         0  0  0  1  0  1  0  1  2  3  4
z         0  0  0  1  0  1  0  4  0  0  1

Почему 2n. Число k растёт на единицу только при совпадении - не больше n раз. Каждый откат его уменьшает. Убавить нельзя больше, чем прибавили.

Z-ФУНКЦИЯ: одна строка даёт все три случая
z[i] = min(r − i, z[i − l])     если i внутри блока, иначе 0
дальше продлеваем сравнениями;  если i + z[i] > r, блок становится [i, i + z[i])

поиск:   z склейки p + "#" + t,   вхождение там, где z[i] = m
период:  наименьший i, где i + z[i] = n          (или m − π[m − 1])

Ловушки джокера

i + m < n вместо i + m <= n. Последняя позиция не проверяется, вхождение в конце текста теряется.

Прыжок на m после находки. abab в abababababab входит пять раз, а не три. Встроенный count считает без перекрытий - это его документированное поведение.

Срез вместо цикла. t[i:i + m] == p платит m на каждой позиции, даже если первый символ не совпал.

Поверить хешу. Без посимвольной проверки Рабин-Карп при q = 13 находит 766 вхождений вместо одного.

Отрицательный остаток. В C, Java, JavaScript, Go -188 % 11 равно -1. Брать (x % q + q) % q.

x^m вместо x^(m−1). Первое окно считается верно, все следующие - мусор.

if вместо while при откате. aaab даёт 0 1 2 1 вместо 0 1 2 0, и образец «находится» там, где его нет.

π[k] вместо π[k − 1]. Последний совпавший символ имеет индекс k − 1.

k = 0 после находки. Теряются перекрывающиеся вхождения.

Z-функция без min. Значение вылезает за край блока: aaa даёт 0 2 2 вместо 0 2 1.

Забытое обновление Z-блока. Ответ верный, цена квадратичная. Ловится только замером.

Разделитель, который есть в тексте. Совпадение перешагивает через него, z становится больше m.

Куда это ведёт

КМП при расхождении делает цепочку откатов, и один символ текста может стоить нескольких сравнений. В следующей главе эта цепочка считается заранее для каждого символа алфавита - получается автомат, который тратит на символ текста ровно одно обращение к таблице. А потом идея разворачивается: если сравнивать образец с конца, часть текста можно не читать вовсе.