Реализации алгоритмов/Алгоритм Бойера — Мура
Внешний вид
Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.
C++
[править]vector<int> prefix_func(const string &s) {
vector<int> p(s.length());
int k = 0;
p[0] = 0;
for (int i = 1; i < s.length(); ++i) {
while (k > 0 && s[k] != s[i]) {
k = p[k - 1];
}
if (s[k] == s[i]) {
++k;
}
p[i] = k;
}
return p;
}
int find(string &s, string &t) {
if (s.length() < t.length()) {
return -1;
}
if (!t.length()) {
return s.length(); //сыс
}
typedef unordered_map<char, int> TStopTable;
typedef unordered_map<int, int> TSufficsTable;
TStopTable stop_table;
TSufficsTable suffics_table;
for (int i = 0; i < t.length(); ++i) {
stop_table[t[i]] = i;
}
string rt(t.rbegin(), t.rend());
vector<int> p = prefix_func(t), pr = prefix_func(rt);
for (int i = 0; i < t.length() + 1; ++i) {
suffics_table[i] = t.length() - p.back();
}
for (int i = 1; i < t.length(); ++i) {
int j = pr[i];
suffics_table[j] = min(suffics_table[j], i - pr[i] + 1);
}
for (int shift = 0; shift <= s.length() - t.length();) {
int pos = t.length() - 1;
while (t[pos] == s[pos + shift]) {
if (pos == 0) return shift;
--pos;
}
if (pos == t.length() - 1) {
TStopTable::const_iterator stop_symbol = stop_table.find(s[pos + shift]);
int stop_symbol_additional = pos - (stop_symbol != stop_table.end() ? stop_symbol->second : -1);
shift += stop_symbol_additional;
} else {
shift += suffics_table[t.length() - pos - 1];
}
}
return -1;
}
Си
[править]Здесь occ
— таблица стоп-символов, skip
— таблица суффиксов. Для ясности листинга применён простейший, требующий O(|needle|²) операций, алгоритм расчёта таблицы суффиксов.
#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;
}