ПОШУК ЗРАЗКА В РЯДКУ
Якщо за деякого k>0 s[k] x[k], то серед x[k-1], … , x[1] треба відшукати найближчий до x[k] символ x[j]=s[k]. Ця рівність означає, що зразок, можливо, має кінець у рядку в позиції k+(n-j), тобто n+(k-j). Тоді можна знову починати все з кінця зразка, порівнюючи x[n] із s[n+(k-j)].
Нехай змінна last позначає позицію кінця зразка в рядку s. Спочатку last=n, а його наступним значенням може бути лише, як показує попередній аналіз, або n+1, або n+(n-p[s[n]]), або n+(k-j). За будь-якого з цих значень змінної last наступним її значенням буде так само або last+1, або last+(last-p[s[n]]), або last+k-j. На основі цих міркувань записується такий спрощений варіант алгоритму Бойєра-Мура:
last:=n;
while last<=m do
if x[n]<>s[last] then last:=last+(n-p[s[n]])
else
begin
k:=n-1; ok:=true;
while (k>0) and ok do
if x[k]=s[last-n+k] then k:=k-1 else ok:=false;
if k=0 then {s[last-n+1]…s[last]=x}
begin
повідомити про те, що з last-n+1 починається зразок;
last:=last+1
end else
begin
відшукати серед x[1]…x[k-1] найближчий до x[k]
символ x[j], рівний s[last-n+k]; якщо такого немає, то j:=0
last:=last+(k-j)
end
end.
Зауважимо, що цей спрощений варіант в деяких випадках не рятує від необхідності здійснювати O(m n) порівнянь символів. Справжній алгоритм Бойєра-Мура забезпечує, що кількість порівнянь символів за будь-яких рядків довжини m і n оцінюється як O(m+n), тобто її можна вважати пропорційною сумі довжин рядка й зразка. Ідея цього методу приблизно така сама, як і методу з наступного підрозділу.
3. Метод Кнута-Морріса-Пратта