Реализации алгоритмов/Алгоритм Бойера — Мура

Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

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;
}