 |
Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.
Tурбо-БМ.
Перевод с английского - Кантор И.
Турбо - БМ является улучшением алгоритма Боуера - Мура. Мы будем запоминать сегмент текста, который сошелся с суффиксом образца во время прошлой попытки ( и только, если произошел сдвиг хорошего суффикса ).Это даст нам два преимущества:
1. Возможность перескочить через этот сегмент
2. Возможность применения 'турбо - сдвига'
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть u - запомненный сегмент, а v - cуффикс, совпавший во время текущей попытки, такой что uzv - суффикс x. Тогда av - суффикс x, два символа а и b встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем турбо - сдвигом ).
Применение турбо-сдвига в случае |v| < |u|.
При |v| < |u|, если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен |u| | 1. В этом случае символы c и d различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший |u| + 1 совместит c и d с одним и тем же символом v. Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный |u| + 1.
Нельзя совместить символы c =/= d с одним и тем же символом v.
Реализация на Си
/* In TBM function variable u memorizes the length of the suffix matched during
the previous attempt and the variable v memorizes the length of the suffix
during the current attempt
*/
/* Preprocessing of the Bad Character function shift */
PRE_BC( char *x, int m, int bm_bc[] ) {
int a, j;
for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m;
for ( j=0; j < m-1; j++ ) bm_bc[ x[ j ] ] = m - j - 1;
}
/* Preprocessing of the Good Suffix function shift */
PRE_GS( char *x, int m, int bm_gs[] ) {
int i, j, p, f[XSIZE];
memset( bm_gs, 0, ( m + 1 ) * sizeof( int ) );
f[ m ] = j = m + 1;
for (i=m; i > 0; i-- ) {
while ( j <= m && x[ i - 1 ] != x[ j - 1 ] ) {
if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = j - 1;
j = f[ j ];
}
f[ i - 1 ] = --j;
}
p=f[ 0 ];
for ( j=0; j <= m; ++j ) {
if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = p;
if ( j == p ) p = f[ p ];
}
}
/* Boyer-Moore string matching algorithm */
void TBM( char *x, char *y, int n, int m ) {
int i, j, u, shift, v, turbo_shift, bm_gs[XSIZE], bm_bc[ASIZE];
/* Preprocessing */
PRE_GS( x, m, bm_gs );
PRE_BC( x, m, bm_bc );
i = u = 0;
shift = m;
while ( i <= n-m ) {
j = m - 1;
while ( j >= 0 && x[ j ] == y[ i + j ] ) {
--j;
if ( u != 0 && j == m - 1 - shift ) j -= u;
}
if ( j < 0 ) {
OUTPUT( i );
shift = bm_gs[ 0 ];
u = m - shift;
}
else {
v = m - 1 - j;
turbo_shift = u - v;
bc_shift = bm_bc[ y[ i+j ] ] - m + j + 1;
shift = MAX ( turbo_shift, bc_shift );
shift = MAX ( shift, bm_gs[ j+1 ] );
if ( shift == bm_gs[ j+1 ]) u = MIN( (m - shift), v );
else {
if ( turbo_shift < bc_shift ) shift = MAX (shift, (u+1) );
u = 0;
}
}
i += shift;
}
}