Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 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 # не нашли

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

Когда то давно, мы уже рассматривали пример решения задачи рекурсивным образом, на примере задачи по размену денег. Пришло время вспомнить некоторые классические подходы и начать хотелось бы с задачи о путешествии шахматного коня.

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

Итак, каждый ход мы будем характеризовать 3-мя числами: его порядковым номером i и парой координат x, y. История ходов будет храниться в матрице списков, в соответствующей ячейке записываем порядковый номер хода. Соответственно, если в ячейке 0, значит туда мы еще не ходили.

Важно определиться с вычислением новой координаты. Можно заметить, что у коня есть 8 позиций-кандидатов (u, v) куда может прыгнуть конь.
Будем получать новые координаты прибавляя соответствующие смещения, хранящиеся в 2х списках dx, dy и отслеживать допустимость хода (находимся в пределах доски).

Характерной чертой данного алгоритма является то, что каждый шаг, выполняемый в попытке приблизиться к полному решению, запоминается таким образом, чтобы от него можно было позднее отказаться, если выяснится, что он не может привести к полному решению. Такое действие называется возвратом. А класс алгоритмов, как не трудно догадаться, алгоритмы с возвратом.

Очень советую читать именно алгоритм, тем более Питон в этом сильно помогает. Это даст куда больше толку. чем множество лишних слов!)

#Задача о коняшке
def knightsTour(x0, y0, done, size=5):
    #создаем шахматную доску в виде 2го списка
    h = [[0 for j in xrange(size)] for i in xrange(size)]
    #начальная координата(1го хода)
    h[x0][y0] = 1
    
    #Возможные ходы
    dx = [2, 1, -1, -2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    def CanBeDone(u, v, i):
        h[u][v] = i
        done = tryNextMove(u, v, i)
        if not done:
            h[u][v] = 0
        return done
    
    def tryNextMove(x,y, i):
        
        #eos - показывает все ли варианты возможных 8ми ходов мы рассмотрели
        #done - показывает удачна ли данная ветка решения
        #k - порядковый номер рассмотренной попытки из 8 допустимых
        env = {'done': False, 'eos': False, 'u': x, 'v': y, 'k': -1}

        def next():
            x = env['u']
            y = env['v']
            while env['k'] < 8:
                env['k'] +=1;
                if env['k'] < 8:
                    env['u'] = x + dx[env['k']]
                    env['v'] = y + dy[env['k']]
                if (env['u'] >= 0 and env['u']=0 and env['v']                    break
            env['eos'] = (env['k']==8)

        if i < size**2:#если доска не заполнена
            next()
            while not env['eos'] and not CanBeDone(env['u'], env['v'], i+1):
                next()
            done = not env['eos']
        else:
            done = True
        return done

    tryNextMove(x0, y0, 1)
    print h

Привожу пример заполнения шахматной доски.

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…

С поиском подстроки мы встречаемся постоянно. Всем любимый ctrl+f, это именно то, что нам нужно.
Часто ли вы задумывались, а как оно работает? Многие из Вас, наверняка, скажут, что если потребуется — сделаем.
Большинство, думаю, решат эту задачу в лоб и для наглядности я покажу, как это сделать.

Прямой поиск, или, как еще часто говорят, «просто взять и поискать» — это первое решение, которое приходит в голову неискушенному программисту. Суть проста: идти по проверяемой строке A и искать в ней вхождение первого символа искомой строки X. Когда находим, делаем гипотезу, что это и есть то самое искомое вхождение. Затем остается проверять по очереди все последующие символы шаблона на совпадение с соответствующими символами строки A. Если они все совпали — значит вот оно, прямо перед нами. Но вот если какой-то из символов не совпал, то ничего не остается, как признать нашу гипотезу неверной, что возвращает нас к символу, следующему за вхождением первого символа из X.

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

Справедливости ради следует отметить, что если строки невелики, то такой алгоритм может работать быстрее «правильных» алгоритмов за счет более предсказуемого с точки зрения процессора поведения.

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

def stringSearch(s, x):
    i=j=0
    lengthS = len(s)# Длина строки в которой ищем
    lengthX = len(x)# -||- которую ищем
    # пока не достигли одного из концов
    while i<=lengthS - lengthX and j>lengthx:
     # если совпали буквы продвигаемся по обеим строкам
        if li[i+j]==x[j]:
            j+=1
        # иначе двигаемся по строке(+1), начиная с 0 символа подстроки
        else:
            i+=1
            j=0
    # если дошли до конца подстроки - нашли, иначе - нет
    return i if j==lengthX else None

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

Используемая литература:

1. Википедия
2. habrahabr

Алгоритм был разработан Кнутом (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»:

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

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 при любой другой букве.
И хотя мы делаем меньше сравнений(пропускаем середину слова), однако весь совпадающий префикс мы проходим, что не есть хорошо.

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