Алгоритм
Алгоритм основан на трёх идеях.
Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.
Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.
Эвристика стоп-символа. Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней буквы «к».
Строка: * * * * * * к * * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.
Строка: * * * * * а л * * * * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.
Строка: * * * * к к о л * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л ?????
В таких ситуациях выручает третья идея АБМ — эвристика совпавшего суффикса.
Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.
Строка: * * т о к о л * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.
Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону. Именно из-за этого алгоритм Бойера-Мура не учитывает совпавший суффикс и несовпавший символ одновременно — это потребовало бы слишком много предварительных вычислений.
#include <string.h>
#include <limits.h>
/* Вход: needle+nlen - что искать
* offset - позиция конца суффикса; suffixlen - его длина
* Выход: 1, если есть совпадение суффикса (и нет совпадения более длинного суффикса)
*/
static int suffix_match(const unsigned char *needle, size_t nlen, size_t offset, size_t suffixlen)
{
if (offset > suffixlen)
return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&
memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;
else
return memcmp(needle + nlen - offset, needle, offset) == 0;
}
static size_t max(size_t a, size_t b)
{
return a > b ? a : b;
}
/* Вход: haystack - где искать, needle - что искать.
* hlen - длина haystack, nlen - длина needle
* Выход: указатель на первое вхождение needle в haystack, либо NULL
*/
const unsigned char* memmem_boyermoore
(const unsigned char* haystack, size_t hlen,
const unsigned char* needle, size_t nlen)
{
size_t skip[nlen]; /* Таблица суффиксов */
size_t occ[UCHAR_MAX + 1]; /* Таблица стоп-символов */
if(nlen > hlen || nlen <= 0 || !haystack || !needle)
return NULL;
/* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */
/* Заполняем -1 (в Си нумерация символов с 0!!) */
for(size_t a=0; a<UCHAR_MAX+1; ++a)
occ[a] = -1;
/* В таблицу occ записывается последнее вхождение в needle */
/* (исключая последний символ) */
for(size_t a = 0; a < nlen - 1; ++a)
occ[needle[a]] = a;
/* ПОСТРОЕНИЕ ТАБЛИЦЫ СУФФИКСОВ */
/* Упрощённый вариант. Можно реализовать быстрее. */
for(size_t a = 0; a < nlen; ++a)
{
size_t offs = nlen;
while(offs && !suffix_match(needle, nlen, offs, a))
--offs;
skip[nlen - a - 1] = nlen - offs;
}
/* ПОИСК */
for(size_t hpos = 0; hpos <= hlen - nlen; )
{
size_t npos = nlen - 1;
/* Сверка needle и haystack с конца */
while(needle[npos] == haystack[npos + hpos])
{
if(npos == 0)
return haystack + hpos;
--npos;
}
/* Не совпало! */
hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
/* ^^^ ^^^^ */
/* суффикс стоп-символ */
}
return NULL;
}