251
правка
Изменения
Нет описания правки
'''Алгоритм Турбо-алгоритм Бойера-Мура за линейное время (Турбо-алгоритм)''' (англ. ''Turbo Boyer-Moore'') является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. АлгоритмТурбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
==Алгоритм==
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен).
Эта методика представляет два преимущества:
# можно перепрыгнуть через этот сегмент;
# она может позволить выполнение 'турбо«турбо-сдвига'сдвига».
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
При <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>.
==Псевдокод==
j -= u
'''if''' (j < 0)
shift = bm_gs[0]
u = m - shift
'''int''' turbo_shift = u - v
'''int''' bc_shift = bm_bc[y[i + j]] - m + j + 1
shift = MAXmax(turbo_shift, bc_shift) shift = MAX(shift, bm_gs[j + 1])
'''if''' (shift == bm_gs[j + 1])
u = MINmin((m - shift), v)
'''else'''
'''if''' (turbo_shift < bc_shift)
shift = MAXmin(shift, (u + 1))
u = 0
i += shift
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
==СсылкиИсточники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [[wikipedia:Boyer–Moore_string_search_algorithm|Wikipedia {{---}} Boyer–Moore string search algorithm]]
