Записки программиста Программирование и не только

Алгоритм Бойера-Мура-Хорспула

Сортировка:
1. Быстрая сортировка (англ. quicksort)
2. Сортировка Шелла (англ. Shell sort)

Поиск:
1. Прямой поиск (он же Простой, он же Алгоритм грубой силы)

И новенькое:
Алгоритм Бойера-Мура-Хорспула

Алгоритм основан на двух идеях :

1. Сравнение искомого слова с текстом начинается с последнего символа.

2. В случае несовпадения символа слово смещается на число знаков, получаемое из таблицы стоп-символов:

2.1. Таблица стоп-символов строится по принципу – каждому символу назначается номер позиции его последнего вхождения в искомое слово. Т.е., например, для слова “asdfsdfd” символу “s” будет соответствовать номер 4 (если считать с 0). Обратите внимание, что для символа “d” номер будет не “7”, а “5”, т.к. последний символ не учитывается.

Длина таблицы соответствует длине алфавита.  В случае с таблицей cp866 (стандартный алфавит для DOSа) длина алфавита равна 256.

И боевой пример:

int boyermooreFind (int _start, arr &src_str, int src_len, arr &find_str, int find_len)
{
    arr occ;				/* Таблица стоп-символов */

    /* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */
    for(int a = 0; a < 2048; a++) occ.push_back(-1);
	for(int a = 0; a <= find_len - 1; a++) occ.at(find_str.at(a)) = a;

    /* ПОИСК! */
    for(int hpos = _start; hpos <= src_len - find_len; )
    {
        int npos = find_len - 1;
        while(find_str.at(npos) == src_str.at(npos + hpos))
        {
            if(npos == 0)
                return hpos;

            npos--;
        }
        /* Не совпало! */
		if (occ.at(src_str.at(npos+hpos)) == -1)
		{
			hpos = hpos + npos + 1 /*find_len*/;
		}
        else
		{
			hpos = hpos + (npos - occ.at(src_str.at(npos + hpos)));
		}
    }
    return -1;
}

int _start - номер начальной позиции для поиска (используется для поиска всех вхождений искомого слова в строку)
arr &src_str - адрес целочисленного массива типа vector - исходный текст
int src_len - длина исходного текста
arr &find_str - адрес целочисленного массива типа vector - искомое слово
int find_len - длина искомого слова