Delphi World - Точный поиск подстроки в строке - Турбо - обращенние сегмента
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Точный поиск подстроки в строке - Турбо - обращенние сегмента

Автор: 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;
   }
}
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования