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

Этот алгоритм является улучшением 'алгоритма обращенного сегмента' уменьшающим наибольшее число сравнений до 2*n. В самом деле, достаточно запомнить префикс u (x), который совпал во время прошлой попытки. Тогда во время текущей попытки при достижении правого конца u, легко доказать, что достаточно прочитать заново не более, чем правую половину u. Это и заложено в алгоритме турбо-обращения сегмента.

Пусть слово z - сегмент слова w. Oпределим смещение disp( z, w) - от англ. displacement как положительное целое число, такое что

w [ m - d - |z| - 1 , m - d ] = z.

Типичная для TRF-алгоритма ( Turbo Reverse Factor - о чем мы говорим) ситуация возникает, когда префикс u был найден при прошлой попытке, а сейчас алгоритм пытается сравнить сегмент v длины m - |u| с текстом сразу справа за u. Точка между u и v называется 'точкой принятия решения'. Если v не является сегментом x, то сдвиг вычисляется, как в простом алгоритме обращенного сегмента.

Если v - суффикс x, тогда мы нашли x, а если v - не суффикс, но сегмент x, то достаточно просмотреть заново min( per( u ) , |u| / 2 ) правых символов u. Если u - периодичное ( т.е per( u ) <= |u| / 2 ), то пусть z - суффикс u длины per( u ). По определению периода, z - непериодичное слово, а значит следующее наложение невозможно:

Таким образом, z может появиться в u лишь на расстоянии, кратном per( u ), и следовательно, наименьший подходяший суффикс uv, являющийся префиксом x имеет длину |uv| - disp( zv , x ) = m - disp( zv , x ), значит, длину сдвига можно положить равной disp( zv , x ).

Если u - не периодичное: per( u ) > |u| / 2, то очевидно, что x не может появиться второй раз в левой части u длины per( u ). А значит, достаточно будет просмотреть правую часть u длины |u| - per( u ) < |u| / 2, чтобы найти неопределенный переход автомата. Функция disp реализована непосредственно в автомате S( x ) без увеличения сложности его построения.

Турбо алгоритм обращения сегмента производит в худшем случае 2*n сравнений и в среднем оптимален.

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

  struct Arrow {
   int target, shift;
};

struct State {
   int length, suf, pos;
   char terminal;
};

typedef struct Arrow ARROW;
typedef struct State STATE;

int state_counter;
int next[ XSIZE + 1 ];
/* Creates and returns a clone of state p. */
int COPY ( int p , STATE *states , ARROW trans[ XSIZE ][ ASIZE ])
{
 int r;
 
 r = state_counter++;
 memcpy( trans[ r ] , trans[ p ] , ASIZE * sizeof( ARROW ));
 states[ r ].suf = states[ p ].suf;
 states[ r ].pos = states[ p ].pos;
 return (r);
}

/* Creates the suffix automation for the reverse of the word x and */
/*  returns its initial state.                              */
int SUFF( char *x, int m, STATE *states, ARROW trans[ XSIZE ][ ASIZE ])
{
 int i, art, init, last, p, q, r;
 char a;
 
 art = state_counter++;
 init = state_counter++;
 states[ init ].suf = art;
 last = init;
 for ( i = m - 1; i >= 0; --i) {
    a = x[ i ];
   p = last;
   q = state_counter++;
   states[ q ].length = states[ p ].length + 1;
   states[ q ].pos = states[ p ].pos + 1;
   while ( p != init && trans[ p ][ a ].target == 0 ) {
      trans[ p ][ a ].target = q;
      trans[ p ][ a ].shift = states[ q ].pos - states[ p ].pos - 1;
      p = states[ p ].suf;
   }
   if ( trans[ p ][ a ].target == 0 ) {
      trans[ init ][ a ].target = q;
      trans[ init ][ a ].shift = states[ q ].pos - 
	                                         states[ init ].pos - 1;
      states[ q ].suf = init;
   }
   else
     if ( states[ p ].length + 1 == 
	                         states[ trans[ p ][ a ].target ].length)
        states[ q ].suf = trans[ p ][ a ].target;
     else {
 r = COPY( trans[ p ][ a ].target , states, trans );
 states[ r ].length = states[ p ].length + 1;
 states[ trans[ p ][ a ].target ].suf = r;
 states[ q ].suf = r;
 while ( p != art && states[ trans[ p ][ a ].target ].length >=
                                               states[ r ].length) {
    trans[ p ][ a ].shift = states[ trans[ p ][ a ].target ].pos - 
	                                            states[ p ].pos - 1;
   trans[ p ][ a ].target = r;
   p = states[ p ].suf;
 }
    }
   last = q;
 }
 states[ last ].terminal = 1;
 p = last;
 while ( p != init ) {
    p = states[ p ].suf;
   states[ p ].terminal = 1;
 }
 return ( init );
}

/* Computation of the Morris and Pratt next function */
int MP( char *x, int m, int mp_next[])
{
 int i, j;
 
 i = 1;
 j = 0;
 mp_next[ 0 ]= -1;
 while ( i < m )
    if ( j > -1 && x[ i ] != x[ j ])
      if ( j ) j = mp_next[ j-1 ] + 1;
      else j = -1;
   else mp_next[ i++ ] = j++;
 for ( i = 0; i < m; ++i ) mp_next[ i ] = i - mp_next[ i ];
 return 0;
}

/* Turbo Reverse Factor algorithm. */
void TRF( char *y, char *x, int n, int m)
{
 int period, i, j, shift, u, period_of_u, disp;
 int init, state, state_aux, mu;
 STATE states[ 2 * XSIZE + 2 ];
 ARROW trans[ XSIZE ][ ASIZE ];
 
 /* Preprocessing */
 memset( trans, 0, 2 * ( m + 2 ) * ASIZE * sizeof ( ARROW ) );
 memset( states, 0, 2 * ( m + 2 ) * sizeof( STATE ) );
 state_counter = 1;
 init = SUFF( x , m , states , trans );
 MP ( x, m, next );
 period = next [ m - 1 ];
 i = period_of_u = 0;
 shift = m;
 
 /* Searching */
 while ( i <= n - m ) {
    j = m - 1;
   state = init;
   u = m - 1 - shift;
   shift = m;
   disp = 0;
   while (j>u && (state_aux=trans[state][y[i+j]].target)!=0) {
      disp += trans[ state ][ y[ i+j ] ].shift;
      state = state_aux;
      if ( states[ state ].terminal ) shift = j;
      j--;
   }
   if ( j > u ) period_of_u = (shift != m ? next[m-1-shift]:0);
   else if ( !disp ) {
      OUTPUT (i);
      shift = period;
      period_of_u = ( shift != m ? next[ m - 1 - period ] : 0 );
   }
   else {
      mu = ( u + 1 ) / 2;
      if ( period_of_u <= mu ) {
         u -= period_of_u;
         while (j>u&&(state_aux=trans[state][y[i+j]].target)!=0) {
            disp += trans[ state ][ y[ i+j ] ].shift;
            state = state_aux;
            if ( states[ state ].terminal ) shift = j;
            j--;
         }
         if (j>u) period_of_u = (shift!=m ? next[m-1-shift] : 0);
            else {
               shift = disp;
               period_of_u = next[ m - 1 - disp ];
            }
         }
         else {
            u -= mu;
            --u;
            while (j>u&&(state_aux=trans[state][y[i+j]].target)!=0) {
               disp += trans[ state ][ y[ i+j ] ].shift;
               state=state_aux;
               if ( states[ state ].terminal ) shift = j;
               j--;
            }
            period_of_u = ( shift != m ? next[ m - 1 - shift ] : 0 );
         }
      }
      i+=shift;
   }
}