251
правка
Изменения
Нет описания правки
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть <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>|uzv| </tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов а <tex>a</tex> и <tex>b </tex> в тексте. Наименьший возможный сдвиг имеет длину <tex>|u| - |v| </tex> ( его мы и называем турбо - сдвигом ).
===Применение турбо-сдвига в случае <tex>|v| < |u|</tex>===
При <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>.
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом v.
==Псевдокод==
==Асимптотики==
* [[Алгоритм Райта]]
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
*[[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
==Ссылки==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [[wikipedia:Boyer–Moore_string_search_algorithm|Wikipedia {{---}} Boyer–Moore string search algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Turbo Boyer-Moore algorithm]
* [http://algolist.manual.ru/search/esearch/turbo_bm.php Турбо Боуер-Мур]
