����� �� �����.

������ ���������.

����� � �������, ��������, �������������������:
������ ����� ��������� � ������.


�������� ������-���

������� � ����������� - ������ �.

      ����� R - ������� ������ ������� m. ������ R i - �������� ������� R ����� ��������� ���������� �������. �� �������� ���������� ��� ���� ����������� ��������� �, ������� ��������� �� ������� i � ������ ( 0 <= j <= m - 1 ):

R i = 0, ���� x[ 0, j ] = y[ i - j, i ]
R i = 1, � ��������������� ������.


     ������ R i+1 ����� ���� �������� �� R i ��������� �������. ��� ���� R i [j] = 0

R i+1 [ j+1 ] = 0, ���� x[ j+1 ] = y[ i+1 ],
R i+1 [ j+1 ] = 1 � ��������������� ������.

�

R i+1 [ 0 ] = 0, ���� x[ 0 ] = y[ i+1 ],
R i+1 [ 0 ] = 1 � ��������������� ������.


     ���� R i+1 [ m-1 ] = 0, ����� �� ����� ����������.

     ������� �� R i � R i+1 ����� ����� ������ ��������� ��������� �������. ��� ������� a �� S, ����� S a - ������� ������ ������� m ����� ���:

��� 0 <= j <= m - 1, S a = 0 <=> x[ j ] = a


     ������ S a ���������� ������� ������� a � ������� x. ������ S a ����� ���� �������� ����� ��������� ������. ����� ������� ���������� R i+1 ������������� �� ���� ��������: ������ � ���:

R i+1 = SHIFT( R i ) OR S y[ i+1 ]


     ������ ����� ������� ������ ����� ������������� �����, ����� ��������� � O( s + m ) ��� ������������� � O( n ) ��� ������, ���������� �� ����� �������� � �������.

���������� �� �� 
 

 void SO( char *y, char *x, int n,  int m )
{
 unsigned int j, state, lim, first, initial; 
 unsigned int T[ASIZE];
 int i; 
 
 if ( m > WORD ) ERROR( "Use pattern size <= word size" ); 
 
 /* Preprocessing */
 
 for ( i=0; i < ASIZE; i++ ) T[i] =~0;
 lim=0; 
 for ( i=0, j=1; i < m; i++, j <<=1 ) {
    T[x[i]]&=~j; 
   lim|=j; 
  }
  lim=~( lim >> 1 ); 
  
  /* Searching */
  
  state=~0;
  for ( i=0; i < n; i++ ) {
      state = ( state << 1 ) | T[y[i]];
     if ( state < lim ) OUTPUT( i-m+1 ); 
   }
}


����� � ������ ���������

����� �� ��������, � ������ ����������. 		������

���������� �������� �������� ������ ����
�������� ������-���� �������� ��������
�������� �����-������ �������� �����-�������-������
�������� �������-������ �� ����� �� ������� ��������
�������� ������-���

SpyLOG