Cтроим автомат ( DFA ): A(x) = (Q, i, T, d). Q - набор всех префиксов х, Q = { e, x0, x0,1, ... , x0,m - 2, x}; i = e T = { x } Для 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  Обсудить в чате