Пусть 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 ); } }  8  Комментарии к статье  8 8  Обсудить в чате