Delphi World - Точный поиск подстроки в строке

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

Точный поиск подстроки в строке - Алгоритм Сдвига-Или

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

Пусть 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 ); 
   }
}