 |
|
Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.
Алгоритм Морриса-Пратта
Перевод с английского - Кантор И.
Этот алгоритм появился в результате тщательного анализа алгоритма грубой силы. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования ( алгоритм грубой силы ее просто выбрасывает ;-( ).Итак, давайте и мы взглянем на него поближе. Оказывается, размер сдвига образца можно увеличить, одновремеменно запомнив части текста, совпадающие с образцом. Это позволит нам избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.
Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.
При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Наиболее длинный такой префикс - граница u ( Он встречается на обоих концах u ). Это приводит нас к следующему алгоритму: пусть mp_next[ j ] - длина границы x[ 0, j - 1 ]. Тогда после сдвига мы можем возобновить сравнения с места y[ i + j ] и x[ j - mp_next[ j ] ] без потери возможного местонахождения образца. Таблица mp_next может быть вычислена за O( m ) перед самим поиском. Максимальное число сравнений на 1 символ - m
Реализация на Си
/* Preprocessing */
void PRE_MP( char *x, int m, int mp_next[] ) {
int i, j;
i=0;
j=mp_next[0]=-1;
while ( i < m ) {
while ( j > - 1 && x[i] != x[j] ) j=mp_next[j];
mp_next[++i]=++j;
}
}
void MP( char *x, char *y, int n, int m ) {
int i, j, mp_next[XSIZE];
/* Preprocessing */
PRE_MP(x, m, mp_next );
/* Searching */
i=j=0;
while ( i < n ) {
while ( j > -1 && x[j] != y[i] ) j=mp_next[j];
i++;
j++;
if ( j >= m ) {
OUTPUT( i - j );
j = mp_next[ j ];
}
}
}