251
правка
Изменения
→Описание алгоритма
===Описание алгоритма===
В [[Алгоритм Бойера-Мура|алгоритм Бойера-Мура]] дополнительно добавится запоминание длины <tex>|u|</tex> сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига <tex>shift</tex>, который мы совершили. Вычислять его будем следующим образом:
* Если текущем шаге у нас подстрока совпала с шаблоном <tex>x</tex>, то <tex>shift = bmGs[0]</tex> (<tex>bmGs[0]</tex> равен периоду шаблона <tex>x</tex>), <tex>|u| = m - shift</tex>.
* Иначе возможны два случая:
** Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда <tex>shift = bmGs[j+1]</tex>, <tex>|u| = min(m - shift, |v|)</tex> (<tex>v</tex> текущая подстрока).
** В противном случае, <tex>|u| = 0)</tex>, <tex>shift = max(turboShift, bCShift)</tex>(<tex>turboShift</tex> длина турбо-сдвига, <tex>bCShift</tex> длина сдвига плохого символа), если турбо-сдвиг меньше сдвига плохого символа, то <tex>shift</tex> должен быть не больше <tex>|u_0| + 1</tex> (<tex>u_0</tex> сегмент текста, рассматриваемый на прошлом шаге).
==Псевдокод==
