 |
|
����� � �������, ��������, �������������������:
������ ����� ��������� � ������.
���������� ��������
������� � ����������� - ������ �.
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);
}
}