Упрощенный алгоритм Бойера-Мура
Прочитав статью об алгоритмах поиска подстроки в строке, я обнаружил, что там не рассказывается об алгоритме Бойера-Мура. Пара слов о нём всё-таки там есть, а именно, говорится, что алгоритм Бойера-Мура заслужил себе звание «алгоритма по умолчанию», потому что он в среднем дает лучшее время поиска (с чем я полностью согласен). Под катом рассказано об упрощенной версии этого алгоритма. В принципе, большинство скорее всего изучало этот алгоритм на 1-м или 2-м курсе ВУЗа (как и я), поэтому они могут пропустить эту статью, ничего нового тут нет.
Алгоритм
Данный алгоритм также известен под названием алгоритм Бойера-Мура-Хорспула. Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.
Таблица смещений
Таблица смещений строится по принципу «пропускать столько символов, сколько возможно, но не более этого». Например, если на каком-то шаге алгоритма последние символы не совпали, и символ, находящийся в исходной строке не присутствует в шаблоне вообще, то понятно, что можно сдвинуться вправо на полную длину шаблона, без каких-либо опасений. В общем случае, каждому символу ставится в соответствие величина, равная разности длины шаблона и порядкового номера символа (если символ повторяется, то берется самое правое вхождение). Ясно, что эта величина будет в точности равна порядковому номеру символа, если считать от конца строки, что и дает возможность смещаться вправо на максимально возможное число позиций.
Иллюстрация
Чтобы стало совсем понятно рассмотрим работу алгоритма на примере:
Пусть исходная строка равна «somestring» и шаблон равен «string». Теперь строим таблицу смещений, она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона):