Схема КМП-пошуку дає справжній виграш тільки тоді, коли при порівнянні символів до розбіжності було деяке число збігів (>1). Лише в цьому випадку образ зміщується більш ніж на одиницю. На жаль, це скоріше виняток, чим правило: збіги зустрічаються значно рідше, ніж розбіжності. Тому виграш від використання КМП-стратегії в більшості випадків пошуку в звичайних текстах дуже незначний.
Метод, про який зараз піде мова, у дійсності не тільки поліпшує обробку найгіршого випадку, але і дає виграш у проміжних ситуаціях. Його запропонували Р. Боуер і Д. Мур приблизно в 1975 р.; називають його БМ-алгоритмом пошуку або БМ-пошуком.
БМ-пошук ґрунтується на незвичайному розумінні – порівняння символів починається з кінця образу, а не з початку. Як і у випадку КМП-пошуку, для образу-рядка створюється масив, у який для кожного символу образу записується число, що визначає на скільки символів буде зміщений образ у випадку розбіжності на цьому символі. У програмному прикладі 5.9 наведена функція БМ-пошуку образу-рядка pв тексті-рядку s.
{===== Програмний приклад 5.9 =====}
іnt BMSearch (char s[N], char p[M])
{ іnt ch, і, і0, j, k, d[128];
іnt lp=strlen(p), ls=strlen(s);
//формується масив d
for(j=0;j<=lp;j++) //lp–фактична довжина образу-рядка
d[int(p[j])]=lp-j;
//Алгоритм пошуку
і=lp;
do
{ j=lp; k=і;
do
{ k--; j–-;
} whіle ((j>=0)&&(p[j]==s[k]));
і=і+d[іnt(р[j])]
} whіle((j>=0)&&(і<=ls));
іf(j<0) return і–lp; else return –1;
}
Умова успішного пошуку j < 0.
В таблиці 5.2 наведено приклади значень образу-рядка і відповідних їм значень масиву d,що були отримані при тестуванні алгоритму ВМ-пошуку.
Таблиця 5.2
Образ і відповідний йому вмісту масиву
| Значення образу | Вміст масиву d [‘A’] [‘B’] [‘C’] [‘D’] [‘E’] |
| ABCDE AAAAA AAAAB AABCD | 5 4 3 2 1 1 0 0 0 0 2 1 0 0 0 4 3 2 1 0 |