Изменения

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

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

57 байт убрано, 23:00, 4 мая 2016
Алгоритм
Пусть <tex>u</tex> — запомненный сегмент, а <tex>v</tex> — cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> — суффикс <tex>x</tex>. Тогда <tex>av</tex> — суффикс <tex>x</tex>, два символа <tex>a</tex> и <tex>b</tex> встречаются на расстоянии <tex>p</tex> в тексте, и суффикс <tex>x</tex> длины <tex>size(uzv)</tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов <tex>a</tex> и <tex>b</tex> в тексте. Наименьший возможный сдвиг имеет длину <tex>size(u) - size(v)</tex> (его мы и называем турбо-сдвигом).[[Файл:Tbm1.png|600px|center]]
===Применение турбо-сдвига в случае size(v) < size(u)===При Тем не менее, при <tex>size(v) < size(u)</tex>, если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна <tex>size(u) + 1</tex>. Действительно, в этом случае два символа <tex>c</tex> и <tex>d</tex> различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем <tex>size(u) +1</tex> будет выравнивать <tex>c</tex> и <tex>d</tex> с таким же символом в <tex>v</tex>, в этом случае длина фактического сдвига должна быть по крайней мере равен <tex>size(u) +1</tex>.
[[Файл:Tbm2.png|600px|center]]
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом в <tex>v</tex>.
===Описание алгоритма===
251
правка

Навигация