Delphi World - Точный поиск подстроки в строке - Построение автомата
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Точный поиск подстроки в строке - Построение автомата

Автор: Thierry Lecroq
Перевод: Кантор И.

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);
   }
}
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования