Алгоритм Боейра и Мура 







MODULE  ADruS193_БМ;
(* Поиск в тексте. Алгоритм Бойера и Мура, раздел *)
    IMPORT  Log := StdLog,  In := i21sysIn,  КМП := ADruS192_KMP;
    
    CONST  Mmax = 10;  Nmax = 1000;
    VAR
        s: ARRAY Nmax OF CHAR;  N: INTEGER;
        p: ARRAY Mmax OF CHAR;  M: INTEGER;

    (* реализация предикатов, определенных в тексте *)
            
    PROCEDURE P ( i, j: INTEGER ): BOOLEAN;  
        VAR  k: INTEGER;
    BEGIN
        k := j;
        WHILE  ( k < M ) & ( s[ i-M+k ] = p[ k ] )  DO  INC( k )  END;
        RETURN  k = M
    END P;
    
    PROCEDURE R ( i: INTEGER ): BOOLEAN; 
        VAR  j: INTEGER;
    BEGIN
        RETURN  P( i, 0 )
    END R;
    
    PROCEDURE Q ( i: INTEGER ): BOOLEAN;
        VAR  k: INTEGER;
    BEGIN
        k := M;
        WHILE  ( k < i ) & ~R( k )  DO  INC( k )  END;
        RETURN  ~( k < i )
    END Q;
    
    (**********************************************************************)
    
    PROCEDURE Search ( IN p, s: ARRAY OF CHAR;  M, N: INTEGER;  OUT r: INTEGER );
        (* поиск образца p длины M в тексте s длины N; M <= Mmax *)
        (* если p найден, то r указывает его позицию в s, иначе r = -1 *)
        VAR  i, j, k: INTEGER;
            d: ARRAY 128 OF INTEGER;
    BEGIN 
        FOR  i := 0  TO  127  DO  d[i] := M  END; 
        FOR  j := 0  TO  M-2  DO  d[ ORD( p[j] ) ] := M-j-1  END;

        (* инвариант цикла Q(i) & P(i-j,j); проверки (показаны красным) вставлены, для ясности с избытком, всюду, где инвариант должен выполняться *)
        i := M; j := M;  k := i;
        ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
        LOOP IF  (j > 0) & (i <= N) & (s[k-1] = p[j-1])  THEN
            ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
            DEC(k); DEC(j);
            ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
        ELSIF  (j > 0) & (i <= N)  THEN
            ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
            i := i + d[ ORD( s[i-1] ) ];  j := M;  k := i;
            ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
        ELSE EXIT END END;
        ASSERT( Q(i) & P(i, j) & (k = i-M+j) );
        
        IF  j = 0  THEN  r := k  ELSE  r := -1  END;
    END Search;

    (*****************************************************************************)
    
    PROCEDURE Проверить*;
        VAR  r: INTEGER;
    BEGIN
        Log.Ln;
        Log.String('Проверяем Бойера-Мура:');  Log.Ln;

        In.Open;  ASSERT( In.done );
        In.String( s );  ASSERT( In.done );  N := LEN( s$ );
        In.String( p );  ASSERT( In.done );  M := LEN( p$ );
        
        Search( p, s, M, N, r );
        
        Log.Int( r );  Log.Ln;
    END Проверить;
    
END  ADruS193_БМ.
Теги: