Алгоритм Бойера-Мура предназначен для решения типовой задачи поиска подстроки в строке. Он считается самым быстрым среди алгоритмов общего назначения, предназначенных для этой задачи. Суть алгоритма - ценой некоторого количества предварительных вычислений над искомой строкой, она сравнивается с исходным текстом не во всех позициях, часть проверок, заведомо не дающих результата, пропускается. Искомый текст индексируется двумя таблицами - таблицей стоп-символов, имеющей длину алфавита и таблицей суффиксов, длина которой соответствует длине шаблона (искомого текста).

Алгоритм неплохо описан в русской "Википедии", предлагается такая его реализация на консольном С++

#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define ALPHABET_LEN 255 /* Длина алфавита */
#define NOT_FOUND patlen /* Метка "не найдено" в таблице стоп-символов */
#define max(a, b) ((a < b) ? b : a)

//using namespace std;

// Таблица стоп-символов: delta1[c] содержит расстояние между последним
// символом образца с кодом c и правым появлением символа c в шаблоне pat
// Если c отсутствует в шаблоне, то delta1[c] = константе NOT_FOUND
// Если c - это символ string[i] и c != pat[patlen-1], мы можем
// сдвинуть i до delta1[c], который будет минимальным расстоянием,
// на которое можно сдвинуть pat вперед, чтобы получить совпадение string[i]
// с некоторым символом шаблона
// Время работы алгоритма = alphabet_len+patlen шагов
void make_delta1 (int *delta1, char *pat, long int patlen) {
 int i;
 for (i=0; i < ALPHABET_LEN; i++) delta1[i] = NOT_FOUND;
 for (i=0; i < patlen-1; i++) delta1[pat[i]] = patlen-1-i;
}

// Истина, если окончание слова, начиная с word[pos] является префиксом слова
int is_prefix (char *word, int wordlen, int pos) {
 int suffixlen = wordlen - pos;
 // Здесь можно также использовать стандартную strncmp()
 int i;
 for (i = 0; i<suffixlen; i++) {
  if (word[i] != word[pos+i]) return 0;
 }
 return 1;
}

// Длина наибольшего окончания слова, заканчивающегося на word[pos].
// Пример: suffix_length("dddbcabc", 8, 4) = 2
int suffix_length (char *word, int wordlen, int pos) {
 // Увеличиваем длину суффикса i до первого расхождения или начала слова
 int i;
 for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
 return i;
}

// Таблица суффиксов: задает несовпадение pat[pos], мы хотим достигнуть
// следующего возможного вхождения всего шаблона, основываясь на
// известных символах от pat[pos+1] до pat[patlen-1].
// Случай 1:
// От pat[pos+1] до pat[patlen-1] не содержится ничего из шаблона,
// следующее вероятное вхождение шаблона начинается дальше.
// Если подстрока pat[pos+1 .. patlen-1], содержит начало
// шаблона, следующее возможное вхождение шаблона найдено (если есть несколько
// префиксов, берется самый длинный). Иначе следующее возможное вхождение
// начинается после символа, соответствующего pat[patlen-1].
// Случай 2:
// Символы от pat[pos+1] до pat[patlen-1] содержатся в шаблоне.
// Несовпадение говорит, что не найден конец соответствия
// Первый цикл - случай 1, второй - случай 2
void make_delta2 (int *delta2, char *pat, long int patlen) {
 int last_prefix_index = patlen-1;
 // Цикл 1
 int p;
 for (p=patlen-1; p>=0; p--) {
  if (is_prefix(pat, patlen, p+1)) last_prefix_index = p+1;
  delta2[p] = last_prefix_index + (patlen-1 - p);
 }
 // Цикл 2
 for (p=0; p < patlen-1; p++) {
  int slen = suffix_length(pat, patlen, p);
  if (pat[p-slen]!=pat[patlen-1-slen]) delta2[patlen-1-slen]=patlen-1-p+slen;
 }
}

char *boyer_moore (char *string, char *pat) {
 long int stringlen = strlen(string);
 long int patlen =strlen(pat);
 int delta1[ALPHABET_LEN];
 make_delta1(delta1, pat, patlen);
 int *delta2 = new int [patlen * sizeof(int)];
 make_delta2(delta2, pat, patlen);
 int i = patlen-1;
 while (i < stringlen) {
  int j = patlen-1;
  while (j >= 0 && (string[i] == pat[j])) {
   --i; --j;
  }
  if (j < 0) {
   delete delta2;
   return string+i+1;
  }
  i += max(delta1[string[i]], delta2[j]);
 }
 delete delta2;
 return NULL;
}

int main (int argc, char *argv[]) {
 char *string="This is a test string for my test program";
 char *pattern="test";
 cout << "Result=" << boyer_moore(string,pattern) << endl;   
 system("PAUSE");
 return EXIT_SUCCESS;
}

гостевая; E-mail