Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Точный поиск подстроки в строке /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Построение автомата - Программирование от RIN.RU
Построение автомата

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);
}
}






 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь