Алгоритм Бойера - Мура

Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

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

Основная идея алгоритм - начать поиск не с начала, а с конца подстроки. Наткнувшись на несовпадение, мы просто смещаем подстроку до самого правого вхождения данного символа.


Пример можете посмотреть в картинке заголовка :)

Можно заметить, что, как и в случае Кнута-Морриса-Пратта, мы так же можем осуществить предкомпиляцию выражения.

Для этого удобно в словарь заносить пары ключ = числовое значение символа(ord), значение = порядковый номер в подстроке.

А вот и реализация:

def bmPredCompil(x):
    d = {}
    lenX = len(x)
    for i in xrange(len(x)):
        # сколько символов с правого края до этой буквы
        d[ord(x[i])] = lenX - i
    return d

Осталось осуществить сам поиск со сдвигом:

def boyerMurSearch(s, x):
    d = bmPredCompil(x)
    # k - проход по s
    # j - проход по x
    # i - место начала прохода по s
    lenX = i = j = k = len(x)
    while j > 0 and i<=len(s):
     # совпали, двигаемся дальше (от конца к началу)
        if s[k-1] == x[j-1]:
            k -= 1
            j -= 1
        # иначе, продвигаемся по строке на d и начинаем с правого конца подстроки снова
        else:
            i += d[ord(s[i])]
            j = lenX
            k = i
    if j <= 0:# нашли
        return k
    return None # не нашли

Вот собственно и все! :)
Реализация, как и сама идея, достаточно прозрачна.