251
правка
Изменения
→Псевдокод
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом v.
==Псевдокод==
Стадия репроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]].
В сам алгоритм добавляется обработка турбо-сдвигов.
'''function''' TBM( '''char'''[] x, '''char'''[] y, '''int''' n, '''int''' m ) {
'''int''' n = length(y)
'''int''' m = length(x)
'''int''' i = 0
'''int''' u = 0
'''int''' shift = m
'''if''' m == 0
'''return'''
<font color=green>//Предварительные вычисления</font>
'''int''' bmBc[] = preBmBc(x, m)
'''int''' bmGs[] = preBmGs(x, m)
'''while''' (i <= n - m)
'''int''' j = m - 1;
'''while''' (j >= 0 && x[j] == y[i + j])
--j;
'''if''' (u != 0 && j == m - 1 - shift)
j -= u
'''if''' (j < 0)
OUTPUT(i);
shift = bm_gs[0];
u = m - shift;
'''else'''
'''int''' v = m - 1 - j;
'''int''' turbo_shift = u - v;
'''int''' bc_shift = bm_bc[y[i+j]] - m + j + 1;
shift = MAX (turbo_shift, bc_shift);
shift = MAX ( shift, bm_gs[j+1]);
'''if''' (shift == bm_gs[j+1])
u = MIN((m - shift), v);
'''else'''
'''if''' (turbo_shift < bc_shift) shift = MAX (shift, (u+1) );
u = 0;
i += shift;
==Асимптотики==
==См. также==
