Поиск по сайту.

Другие алгоритмы.

Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.


Алгоритм Сдвига-Или

Перевод с английского - Кантор И.

      Пусть R - битовый массив размера m. Вектор R i - значение массива R после обработки очередного символа. Он содержит информацию обо всех совпадениях префиксов х, которые кончаются на позиции i в тексте ( 0 <= j <= m - 1 ):

R i = 0, если x[ 0, j ] = y[ i - j, i ]
R i = 1, в противоположном случае.


     Вектор R i+1 может быть вычислен по R i следующим образом. Для всех R i [j] = 0

R i+1 [ j+1 ] = 0, если x[ j+1 ] = y[ i+1 ],
R i+1 [ j+1 ] = 1 в противоположном случае.

И

R i+1 [ 0 ] = 0, если x[ 0 ] = y[ i+1 ],
R i+1 [ 0 ] = 1 в противоположном случае.


     Если R i+1 [ m-1 ] = 0, тогда мы нашли совпадение.

     Переход от R i к R i+1 можно очень быстро вычислить следующим образом. Для каждого a из S, пусть S a - битовый массив размера m такой что:

Для 0 <= j <= m - 1, S a = 0 <=> x[ j ] = a


     Массив S a обозначает позиции символа a в образце x. Каждый S a может быть вычислен перед процессом поиска. Тогда процесс вычисления R i+1 укорачивается до двух операций: СДВИГА и ИЛИ:

R i+1 = SHIFT( R i ) OR S y[ i+1 ]


     Считая длину образца меньше длины компьютерного слова, можно уложиться в O( s + m ) для предобработки и O( n ) для поиска, независимо от длины алфавита и образца.

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

 void SO( char *y, char *x, int n,  int m )
{
 unsigned int j, state, lim, first, initial; 
 unsigned int T[ASIZE];
 int i; 
 
 if ( m > WORD ) ERROR( "Use pattern size <= word size" ); 
 
 /* Preprocessing */
 
 for ( i=0; i < ASIZE; i++ ) T[i] =~0;
 lim=0; 
 for ( i=0, j=1; i < m; i++, j <<=1 ) {
    T[x[i]]&=~j; 
   lim|=j; 
  }
  lim=~( lim >> 1 ); 
  
  /* Searching */
  
  state=~0;
  for ( i=0; i < n; i++ ) {
      state = ( state << 1 ) | T[y[i]];
     if ( state < lim ) OUTPUT( i-m+1 ); 
   }
}