|
Построение автомата
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, deltaXSIZEASIZE;
/* Preprocessing *.
memset(delta, 0, ASIZE*sizeof(int));
for (j=0; j < m; j++) {
i=deltajxj;
deltajxj=j+1;
memcpy(deltaj+1, deltai, ASIZE*sizeof(int));
}
/* Searching */
j=0;
for (i=0; i < n; i++) {
j=deltajyi;
if (j >= m) OUTPUT(i-m+1);
}
}
|
| |