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

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

Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые 'напоминают' образец. Для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию хеширования. Она должна удовлетворять следующим требованиям:

1. Легко вычисляться.
2. Как можно лучше различать несовпадающие строки.
3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ] ):

hash( y[ i+1 , i+m ] ) = rehash( y[ i ], y[ i+m ], hash( y[ i , i+m-1]).

Пусть наша функция будет определена для слова w, например, следующим образом:

hash( w[ 0 , m-1 ] ) = ( w[0] * 2 m-1 + w[1] * 2 m-2 + ... + w[m-1] ) mod q,

где q - большое число. Тогда

rehash( a, b, h ) = (( h - a * 2 m-1 ) * 2 + b) mod q.

Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

Наихудший случай O( n * m ) встретится, например, при поиске a m в a n .

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

/* 
   Here all the modulo multiplications by 2 are made using shifts. 
   So q = max integer avianable
*/

#define REHASH( a, b, h ) ((( h - a * d ) << 1 ) + b )

void KR( char *y, char *x, int n, int m ) {
 int hy, hx, d, i;
 
 /*
   Preprocessing
   computes d = 2^( m-1 ) with the left-shift operator
  */
  d = 1;
  for ( i = 1; i < m; i++ ) d = ( d << 1 );
  
  hy = hx = 0;
  for ( i = 0; i < m; i++) {
      hx = ( ( hx << 1 ) + x[i] ); 
     hy = ( ( hy << 1 ) + y[i] );
   }
   
 /* Searching */
 
 for ( i=m; i < n; i++ ) {
      if ( hy == hx && memcmp( &y[ i-m-1 ], x, m ) == 0 ) OUTPUT( i-m ); 
     hy = REHASH( y[i-m], y[i], hy ); 
    }
  } 
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования