Автор: Thierry Lecroq
Перевод: Кантор И.

Турбо - БМ является улучшением алгоритма Боуера - Мура. Мы будем запоминать сегмент текста, который сошелся с суффиксом образца во время прошлой попытки ( и только, если произошел сдвиг хорошего суффикса ).

Это даст нам два преимущества:

1. Возможность перескочить через этот сегмент
2. Возможность применения 'турбо - сдвига'

Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.

Пусть u - запомненный сегмент, а v - cуффикс, совпавший во время текущей попытки, такой что uzv - суффикс x. Тогда av - суффикс x, два символа а и b встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем турбо - сдвигом ).

Применение турбо-сдвига в случае |v| < |u|.

При |v| < |u|, если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен |u| | 1. В этом случае символы c и d различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший |u| + 1 совместит c и d с одним и тем же символом v. Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный |u| + 1.

Нельзя совместить символы c =/= d с одним и тем же символом v.

Реализация на Си

/* In TBM function variable u memorizes the length of the suffix 
  matched during  the previous attempt and the variable v
   memorizes the length of the suffix  during the current attempt
*/

/* Preprocessing of the Bad Character function shift */
PRE_BC( char *x, int m, int bm_bc[] ) {
   int a, j; 
   
   for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m; 
   for ( j=0; j < m-1;  j++ ) bm_bc[ x[ j ] ] = m - j - 1; 
  }
 
 /* Preprocessing of the Good Suffix function shift  */
 PRE_GS( char *x, int m,  int bm_gs[] ) {
   int i, j, p, f[XSIZE];
   
   memset( bm_gs, 0, ( m + 1 ) * sizeof( int ) );
   f[ m ] = j = m + 1; 
   for (i=m; i > 0; i-- ) {
      while ( j <= m && x[ i - 1 ] != x[ j - 1 ] ) {
        if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = j - 1;
       j = f[ j ];
     }
     f[ i - 1 ] = --j; 
   }
   p=f[ 0 ]; 
   for ( j=0; j <= m; ++j ) {
      if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = p; 
     if ( j == p ) p = f[ p ]; 
   }
}

/* Boyer-Moore string matching algorithm */
void TBM( char *x, char *y, int n, int m ) {
  int i, j, u, shift, v, turbo_shift, bm_gs[XSIZE], bm_bc[ASIZE];
  
  /* Preprocessing */
  PRE_GS( x, m, bm_gs ); 
  PRE_BC( x, m, bm_bc );
  
  i = u = 0;
  shift = m;
  while ( i <= n-m ) {
     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 {
      v = m - 1 - j;
      turbo_shift = u - v;
      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;
 }
}