251
правка
Изменения
Нет описания правки
===Описание алгоритма===
В [[Алгоритм Бойера-Мура|алгоритм Бойера-Мура]] дополнительно добавится запоминание длины <tex>|u|</tex> сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига <tex>shift</tex>, который мы совершили. Вычислять его будем следующим образом:
* Если текущем шаге у нас подстрока совпала с шаблоном <tex>x</tex>, то <tex>\mathrm{shift } = bmGs[0]</tex> (<tex>bmGs[0]</tex> равен периоду шаблона <tex>x</tex>), <tex>|u| = m - \mathrm{shift}</tex>.
* Иначе возможны два случая:
** Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда <tex>\mathrm{shift } = bmGs[j+1]</tex>, <tex>|u| = \min(m - \mathrm{shift}, |v|)</tex>, где <tex>v</tex> {{---}} текущая подстрока.** В противном случае, <tex>|u| = 0</tex>, <tex>\mathrm{shift } = \max(\mathrm{turboShift}, \mathrm{bCShift})</tex>, где <tex>\mathrm{turboShift}</tex> {{---}} длина турбо-сдвига, <tex>\mathrm{bCShift}</tex> {{---}} длина сдвига плохого символа. Если турбо-сдвиг меньше сдвига плохого символа, то <tex>\mathrm{shift}</tex> должен быть не больше <tex>|u_0| + 1</tex>, где <tex>u_0</tex> {{---}} сегмент текста, рассматриваемый на прошлом шаге.
==Псевдокод==
Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], функция вычислений сдвигов плохих символов и функция вычисления хороших суффиксов не меняются, меняется только сам алгоритм, в него добавляется обработка турбо-сдвигов.
<font color=green>//x - шаблон, y - текст, m - длина шаблона, n - длина текста</font> '''function''' TBM('''char'''[] x, '''char'''[] y, '''int''' nm, '''int''' mn): '''List<int>'''
'''int''' i = 0
'''int''' u = 0
'''int''' shift = m
<font color=green>//answer - массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном</font> '''List<int>''' answer;
'''if''' (m == 0)
