Префикс-функция и КМП: поиск, который не возвращается по тексту

Если ты посчитаешь префикс-функцию для aabaaab, объяснишь, почему при расхождении берут π[k − 1], и докажешь оценку 2n, - листай до «Теперь сам».

Как думаешь, на сколько можно сдвинуть образец

Образец abracadabra приложен к тексту. Первые десять символов совпали - в тексте стоит abracadabr, - а одиннадцатый не совпал. Наивный поиск сдвинет образец на одну позицию и начнёт сравнивать с начала.

Прежде чем читать дальше, подумай: десять символов текста ты уже знаешь, не заглядывая в него, - это abracadabr. На сколько позиций можно сдвинуть образец сразу, и с какого символа образца продолжить сравнение?

На что это похоже

Представь домофон, который открывается кодом 1213 и не требует сброса: он просто слушает поток цифр. Ты нажал 1, 2, 1 - и ошибся, нажал 2 вместо 3. Начинать ли сначала?

Нет. Последние две нажатые цифры - 1, 2 - это начало правильного кода. Домофон уже на полпути: осталось нажать 1, 3. Он не запоминает всё нажатое и не перематывает назад. Он помнит одно число: сколько цифр кода сейчас набрано. После ошибки это число не обнуляется, а падает до длины самого длинного начала кода, которым заканчивается только что набранное.

Механизм: грань и что помнит префикс-функция

Грань строки - её начало, которое одновременно является её концом и короче самой строки. У строки abra грань одна - a. У abracadabra две: abra и a. У abc граней нет.

Префикс-функция образца p - список π той же длины: π[i] - длина самой длинной грани куска p[0..i], то есть первых i + 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

π[9] = 3:   a b r a c a d a b r        начало abr = конец abr
            ─────         ─────

Теперь поиск. Пусть k - сколько символов образца совпало с текстом к этому моменту. Пришёл новый символ текста, и он не равен p[k]. Совпавшие k символов текста известны: это p[0..k−1]. Следующее вхождение может начинаться только там, где конец этого куска совпадает с началом образца, - иначе расхождение случится ещё на известных символах. Самый длинный такой конец имеет длину π[k − 1], и брать надо именно его: самая длинная грань - это самый маленький сдвиг, а всякий сдвиг меньше дал бы расхождение на уже известных символах. Значит, k падает до π[k − 1], и тот же символ текста сравнивается с p[k] заново. Не подошёл - снова k = π[k − 1]: это грань грани. Она же - следующая по длине грань всего совпавшего куска: любая его грань короче самой длинной стоит и в начале, и в конце этой самой длинной, то есть является её гранью. Поэтому цепочка откатов перебирает все грани от длинной к короткой и ни одной не пропускает.

текст     … a b r a c a d a b r X …        совпало k = 10, X ≠ a
образец     a b r a c a d a b r a
                          ↓ k = π[9] = 3: сдвиг на 10 − 3 = 7
образец                   a b r a c …      X сравнивается с p[3] = a

Это ответ на вопрос из начала: сдвиг на семь позиций, продолжать с четвёртого символа образца. Указатель в тексте при этом не двигается назад ни разу.

Внимательный глаз заметит странность: про X уже известно, что он не a, а p[3] - тоже a, так что это сравнение обречено. Алгоритм этого не помнит и честно сравнивает; на оценку числа сравнений это не влияет. Есть уточнённая таблица, которая такие заведомо неудачные попытки пропускает, - суть та же.

Правило

При расхождении после k совпавших символов КМП заменяет k на π[k − 1] и сравнивает тот же символ текста снова; при k = 0 переходит к следующему символу текста. После найденного вхождения k тоже становится π[m − 1], а не нулём - иначе теряются перекрывающиеся вхождения. Префикс-функция считается тем же приёмом за O(m): образец ищется в самом себе. Весь поиск делает не больше 2n сравнений и ни разу не возвращается по тексту.

Разбор: считаем префикс-функцию для abababca

def prefiks(p):
    m = len(p)
    pi = [0] * m
    k = 0                             # длина грани предыдущего куска
    i = 1
    while i < m:
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]             # грань не продолжилась - берём грань грани
        if p[i] == p[k]:
            k = k + 1                 # грань продолжилась на один символ
        pi[i] = k
        i = i + 1
    return pi

Мысль одна: грань куска p[0..i] получается из грани куска p[0..i−1] дописыванием одного символа. Если p[i] равен символу сразу за старой гранью - грань выросла на единицу. Если нет - пробуем продолжить грань покороче.

i   p[i]   k до    что происходит                              π[i]
1    b      0      b ≠ p[0] = a                                  0
2    a      0      a = p[0]                                      1
3    b      1      b = p[1]                                      2
4    a      2      a = p[2]                                      3
5    b      3      b = p[3]                                      4
6    c      4      c ≠ p[4] = a → k = π[3] = 2
                   c ≠ p[2] = a → k = π[1] = 0
                   c ≠ p[0] = a                                  0
7    a      0      a = p[0]                                      1

Итог: [0, 0, 1, 2, 3, 4, 0, 1]. Шаг i = 6 показывает цепочку откатов: грань abab не продолжилась символом c, её собственная грань ab тоже, а короче граней нет - и с самого начала образца c тоже не совпал.

Разбор: поиск и замер против наивного

Версия со счётчиком: каждый круг внутреннего цикла - ровно одно сравнение символа текста с символом образца.

def kmp(t, p):
    pi = prefiks(p)
    m = len(p)
    k = 0                             # сколько символов образца сейчас совпало
    sravn = 0
    nashli = 0
    i = 0
    while i < len(t):
        while True:
            sravn = sravn + 1
            if t[i] == p[k]:
                k = k + 1
                break
            if k == 0:
                break
            k = pi[k - 1]             # откат по образцу; i не меняется
        if k == m:
            nashli = nashli + 1       # вхождение кончается в позиции i
            k = pi[k - 1]
        i = i + 1
    return [nashli, sravn]

Те же данные, что в уроке про наивный поиск, n = 1000:

текст и образец                         наивный        КМП
"a" * 1000,  "a" * 9   + "b"              9 910       1 991
"a" * 1000,  "a" * 99  + "b"             90 100       1 901
"a" * 1000,  "a" * 499 + "b"            250 500       1 501
tekst(1000, 4, 1),  t[500:510]            1 328       1 248
tekst(1000, 26, 1), t[500:510]            1 046       1 044

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

И граница, которую видно в двух нижних строках таблицы: на обычном тексте КМП почти ничего не выигрывает - 1248 против 1328, 1044 против 1046. Наивный поиск там и так линеен. КМП покупает не скорость на типичных данных, а ГАРАНТИЮ на любых - и за неё платит подготовкой образца и списком из m чисел.

Что ломается без этого

Первое: if вместо while при откате. Один откат вместо цепочки. На многих образцах ответ верный: второй откат подряд нужен редко. На образце aaab префикс-функция выходит 0 1 2 1 вместо 0 1 2 0, и поиск с такой таблицей находит то, чего нет: в тексте aaabaab образец «найден» дважды, хотя входит один раз.

Второе: k = pi[k] вместо k = pi[k − 1]. Совпало k символов, последний из них имеет индекс k − 1, и грань нужна для куска, который кончается на нём. Ошибка на единицу здесь даёт неверные сдвиги, а на образце aaaa - вечный цикл: π[1] = 1, и при откате k не уменьшается.

Третье: k = 0 после находки. В тексте abababababab образец abab входит пять раз; с обнулением найдётся три. Если же не менять k вовсе, следующий круг прочитает p[m] и упадёт с IndexError.

Четвёртое: префикс-функция по определению. Перебрать для каждого i все длины грани и сравнить начало с концом срезами - это O(m³). Для образца в десять символов разницы нет, для тысячи - миллиард действий на подготовку, которая должна стоить тысячу.

Зачем это в работе

Первый сюжет - поток. КМП не возвращается по тексту, значит текст можно не хранить: читать из сети, из канала, с ленты - по символу, держа в памяти одно число k. Наивному поиску при расхождении нужны предыдущие m − 1 символов, их приходится держать в буфере.

Второй - сама префикс-функция как инструмент. Число m − π[m − 1] - длина самого короткого периода строки, то есть куска, повторением которого она получается (последний повтор может быть обрезан): у abababab последнее значение π равно 6, период 8 − 6 = 2. Если период делит длину нацело, строка целиком составлена из повторов одного куска - и это проверено без перебора всех делителей длины.

Третий - фундамент. Поиск сразу многих образцов (алгоритм Ахо-Корасика, через главу) - это та же идея отката, перенесённая со строки на дерево. Кто понял π[k − 1], там не встретит ничего нового, кроме структуры данных.

Теперь сам

Посчитай префикс-функцию для aabaaab. Затем ответь: образец приложен к тексту, совпало шесть символов, седьмой не совпал. Каким станет k и на сколько позиций сдвинулся образец?

индекс    0  1  2  3  4  5  6
образец   a  a  b  a  a  a  b
π         0  1  0  1  2  2  3