Этот алгоритм - некоторое упрощение стандартного Боуера - Мура. В 1980 году Хорспул ( Horspool ) предложил использовать только сдвиг по самому правому символу для вычисления сдвига в алгоритме Боуера - Мура. Получившийся алгоритм имеет квадратичную скорость в худшем случае,но было доказано, что среднее число сравнений на символ текста находится между 1 / |s| и 2 / ( |s| + 1 ). Реализация на С void HORSPOOL( char *y , сhar *x ,int n , int m ) { int a, i, j, bm_bc[ ASIZE ]; char ch, lastch; /* Preprocessing */ for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m; for ( j=0; j < m-1; j++ ) bm_bc[ x[ j ] ] = m - j - 1; /* Searching */ lastch = x[ m-1 ]; i = 0; while ( i <= n-m ) { ch = y[ i + m - 1 ]; if ( ch == lastch ) if ( memcmp( &y[ i ], x, m-1 ) == 0 ) OUTPUT( i ); i += bm_bc[ ch ]; } }  8  Комментарии к статье  8 8  Обсудить в чате