Алгоритм Кнута-Морриса-Пратта (КМП)

Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

Он относится к "правильным" подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.

Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Для понимания: Префикс строки A[..i] — это строка из i первых символов строки A. Суффикс строки A[j..] — это строка из |A|-j+1 последних символов. Подстроку из Aбудем обозначать как A[i..j], а A[i] — i-ый символ строки. 

В статье http://habrahabr.ru/post/111449/ сказано:

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: "AAAAB", где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.

Для реализации данного алгоритма, нам необходимо рассмотреть, так называемую, префикс функцию.

Префикс-функция - это массив чисел, вычисляющийся, как наибольшая длина суффикса, совпадающего с её префиксом. Как пример, берем каждый возможный префикс строки и смотрим самое длинное совпадение начала с концом префикса (не учитывая тривиальное совпадение самого с собой).

Вот пример для «ababcaba»:

суффикс	префикс	p
a	a	0
ab	ab	0
aba	aba	1
abab	abab	2
ababc	ababc	0
ababca	ababca	1
ababcab	ababcab	2
ababcaba	ababcaba	3

Итак, идея ясна? Ну тогда попробум написать префикс функцию в лоб:

def predkompil(x):
    #первый символ всегда 0, поэтому заносим и пропускаем
    d = {0:0}
    for i in xrange(1,len(x)):
     # проходоим от конца к началу
        j = i
        sdvig = 0
        while j>0:
            j -= 1
            if x[j] == x[i-sdvig]:
                sdvig += 1
            else:
                j += sdvig
                sdvig = 0
        d[i] = sdvig
    return d

Вроде работает, но как то много сравнений и проходов. Попробуем оптимизировать.
Начать можно с замены строки j = i, на j = d[i-1]+1.

Что нам это дает? А то, что незачем просматривать каждый раз с конца и до начала.  Можно заметить, что если мы на предыдущем шаге (i-1) нашли вхождение > 0 (d[i-1]), то и начинать стоит с данной позиции (d[i-1]).

Пример:

При i=4 ABAAB -> 2, тогда на i+1, т.е. i=5  смотрим не с j=i(5), а с 3! Т.к. либо счетчик вырастет и станет 3 в случае ABAABA, либо сбросится в 0 при любой другой букве.
И хотя мы делаем меньше сравнений(пропускаем середину слова), однако весь совпадающий префикс мы проходим, что не есть хорошо.


Это уже не плохо, однако, мы с Вами так и не научились использовать  информацию, полученную на предыдущих итерациях.

Зная длину совпадения префикса с суффиксом по предыдущей букве, мы можем начать поиск сразу с этой позиции (d[j-1]) и продвигаясь вперед либо увеличивать данное значение (суффикс равный префиксу продолжит свой рост), либо обнуляется (нет совпадения).

def predkompil2(x):
    d = {0:0}
    for i in xrange(1,len(x)):
        j = d[i-1]#эту строку мы заменили
        while j > 0 and x[j] <> x[i]:
            j = d[j-1]
        if x[j] == x[i]:
            j += 1
        d[i] = j
    return d

В статье на хабре, вы можете ознакомиться с так называемой z-функцией.
Идея её очень схожа с префикс функцией, поэтому её реализацию я опущу :)

Итак, префикс функция готова, осталось применить её и решить поставленную задачу.

def kmpSearch(s, x):
    d = predkompil2(x)
    i = j = 0
    while i<len(s) and j<len(x):
        if x[j] == s[i]:
            i+=1
            j+=1
        elif j==0:
            i+=1
        else:
            j = d[j-1]
    else:
        if j == len(x):
            return i-j
        return None

Вот такая идея описывается в книге Вирта, зная значения префикс ф-ии сдвигаться на заданное расстояние, однако кто-то мог заметить, что для решения задачи, нам достаточно было использовать только префикс функцию. Для этого достаточно сделать конкатенацию искомой подстроки, со строкой, через разделитель, заведомо уникальный(что-то вроде #) и применив префикс ф-ию. Если она даст значение равное длине искомой подстроки, значит мы нашли это место иначе - нет.

def kmpSearchByCompil(s, x):
    d = {0:0}
    template = x + '#' + s
    for i in xrange(1,len(template)):
        j = d[i-1]#незачем смотреть всю строку, можно посмотреть со сдвига прошлой подстроки
        while j > 0 and template[j] <> template[i]:
            j = d[j-1]
        if template[j] == template[i]:
            j += 1
        d[i] = j
        if j == len(x):
            return i
    return None 

Надеюсь, идея понятна.
Мы рассмотрели с Вами один из "правильных" алгоритмов поиска подстроки, однако, классикой данной задачи стал алгоритм Бойера - Мура.
Автор статьи на Хабре утверждает, что он достаточно не тривиален и запутан, однако вынужден с ним не согласиться, что и покажу в следующей заметке.