БМ-алгоритм пошуку рядка в тексті

Схема КМП-пошуку дає справжній виграш тільки тоді, коли при порівнянні символів до розбіжності було деяке число збігів (>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

Аналіз пошуку по Боуеру і Муру. Його чудова властивість полягає у тому, що майже завжди, крім спеціально складених прикладів, він вимагає значно менше N порівнянь. За найсприятливіших обставин, коли останній символ образу завжди потрапляє на незбіжний символ тексту, число порівянь дорівнює N/M.