Автор: Thierry Lecroq Перевод с английского - Кантор И.
Алгоритмы типа Боуера - Мура сравнивают несколько суффиксов образца, но можно сравнивать префиксы образца, читая символы из 'окошка' cправа налево и, тем самым, увеличить длину сдвигов. Это можно реализовать, используя наименьший суффиксный автомат обращенного образца ( smallest suffix automation of reverse pattern).
Наименьший суффиксный автомат слова w - конечный, детерменированный автомат S( w ) = ( Q, i, T, d ). Язык, используемый S( w ) - L( S( w ) ) = { u из S, для которых существует v из S такой что w = vu }.
Фаза предварительной обработки состоит из вычисления наименьшего суффиксного автомата для обращенного образца xR. Это занимает линейное время и линейное количество памяти относительно длины образца.
Во время поиска алгоритм просматривает символы из 'окошка' справа налево, используя автомат S( xR ), запускающийся с состояния i. Так продолжается, пока не окажется, что для текущего символа 'окошка' больше не определено переходов с текущего состояния или пока не будет просмотрено все 'окошко'.
В этот момент легко узнать, какова длина наибольшего префикса образца, с которым идет сравнение: она отвечает длине пути, взятого в S( xR ) от начального состояния i до последнего конечного состояния. Зная длину этого наибольшего префикса, можно тривиально вычислить правильный сдвиг.
Данный алгоритм имеет квадратичный худший случай, однако в среднем оптимален. Он совершает в среднем O ( n*( logsm ) / m ) сравнений символов, достигая наилучшей грани, которую в 1979 году открыл Яо ( Yao ).
Реализация на Си
struct State {
int length, suf, pos;
char terminal;
};
typedef struct State STATE;
int state_counter;
/* Creates and returns a clone of state p. */
int COPY ( int p , STATE states[] , int trans[ XSIZE ][ ASIZE ])
{
int r;
r = state_counter++;
memcpy( trans[ r ] , trans[ p ] , ASIZE * sizeof( int ));
states[ r ].suf = states[ p ].suf;
states[ r ].pos = states[ p ].pos;
return (r);
}
/* Creates the suffix automation for the reverse of the word x and */
/* returns its initial state. */
int SUFF( char *x, int m, STATE states[], int trans[ XSIZE ][ ASIZE ])
{
int i, art, init, last, p, q, r;
char a;
art = state_counter++;
init = state_counter++;
states[ init ].suf = art;
last = init;
for ( i = m - 1; i >= 0; --i) {
a = x[ i ];
p = last;
q = state_counter++;
states[ q ].length = states[ p ].length + 1;
states[ q ].pos = states[ p ].pos + 1;
while ( p != init && trans[ p ][ a ] == 0 ) {
trans[ p ][ a ] = q;
p = states[ p ].suf;
}
if ( trans[ p ][ a ] == 0 ) {
trans[ init ][ a ] = q;
states[ q ].suf = init;
}
else
if ( states[ p ].length + 1 == states[ trans[ p ][ a ] ].length)
states[ q ].suf = trans[ p ][ a ];
else {
r = COPY( trans[ p ][ a ], states, trans );
states[ r ].length = states[ p ].length + 1;
states[ trans[ p ][ a ] ].suf = r;
states[ q ].suf = r;
while ( p != art && states[ trans[ p ][ a ] ].length >=
states[ r ].length) {
trans[ p ][ a ] = r;
p = states[ p ].suf;
}
}
last = q;
}
states[ last ].terminal = 1;
p = last;
while ( p != init ) {
p = states[ p ].suf;
states[ p ].terminal = 1;
}
return ( init );
}
/* Reverse Factor Algorithm. */
int RF( char *y, char *x, int n, int m)
{
int i, j, shift, period, init, state, state_aux;
STATE states[ 2 * XSIZE + 2 ];
int trans[ XSIZE ][ ASIZE ];
/* Preprocessing */
memset( trans, 0, 2 * ( m + 2 ) * ASIZE * sizeof ( int ) );
memset( states, 0, 2 * ( m + 2 ) * sizeof( STATE ) );
state_counter = 1;
i = 0; period = m;
/* Construction of the minimal suffix of the reverse of x */
init = SUFF( x , m , states , trans );
/* Searching */
while ( i <= n - m ) {
j = m - 1;
state = init;
shift = m;
while ( ( state_aux = trans[ state ][ y[ i+j ] ]) != 0) {
state = state_aux;
if ( states[ state ].terminal) {
period = shift;
shift = j;
}
j--;
}
if ( j < 0 ) {
OUTPUT ( i );
shift = period;
}
i += shift;
}
}
