Изменения

Перейти к: навигация, поиск

Турбо-алгоритм Бойера-Мура

410 байт добавлено, 20:20, 25 апреля 2016
Применение турбо-сдвига в случае |v| < |u|
===Применение турбо-сдвига в случае |v| < |u|===
При <tex>|v| < |u|</tex>, если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна <tex>|u| + 1</tex>. Действительно, в этом случае два символа с <tex>c</tex> и <tex>d </tex> различны, так как мы предположили, что предыдущий сдвиг был сдвиг сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем <tex>|u| +1</tex> будет выравнивать <tex>c</tex> и <tex>d</tex> с таким же символом в <tex>v</tex>, в этом случае длина фактического сдвига должна быть по крайней мере равен <tex>|u| +1</tex>.
[[Файл:Tbm2.png|800px|center]]
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом <tex>v</tex>.
251
правка

Навигация