Поиск по сайту.


Другие алгоритмы.

Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.


Построение автомата

Перевод с английского - Кантор И.

     Cтроим автомат ( DFA ): A(x) = (Q, i, T, d).

     1. Q - набор всех префиксов х, Q = { e, x0, x0,1, ... , x0,m - 2, x};

     2. i = e

     3. T = { x }

     4. Для q из Q и a из S, (q, a, qa) принадлежит d, если qa - также префикс x. В противном случае (q, a, p) принадлежит d, такое, что p - длиннейший суффикс qa, являющийся префиксом x.

     После построения автомата, процесс поиска состоит в проходе по тексту и изменению состояний автомата. Каждый раз, когда достигнуто конечное состояние, мы имеем местонахождение образца.

Реализация на Си

void AUT(char *y, char *x, int n, int m)
{
 int i, j, delta[XSIZE][ASIZE];
 
 /* Preprocessing *.
 memset(delta, 0, ASIZE*sizeof(int));
 for (j=0; j < m; j++) {
    i=delta[j][x[j]];
   delta[j][x[j]]=j+1;
   memcpy(delta[j+1], delta[i], ASIZE*sizeof(int));
 }
 
 /* Searching */
 j=0;
 for (i=0; i < n; i++) {
    j=delta[j][y[i]];
   if (j >= m) OUTPUT(i-m+1);
   }
}
   



Построение автомата Алгоритм грубой силы
Алгоритм Боуера-Мура Алгоритм Хорспула
Алгоритм Карпа-Рабина Алгоритм Кнута-Морриса-Пратта
Алгоритм Морриса-Пратта Не такой уж наивный алгоритм
Алгоритм Сдвига-Или