Простой поиск образца в тексте (string search) 








MODULE  ADruS191_Простой; 
(* Поиск в тексте. Простой алгоритм *)

    IMPORT  Log := StdLog,  In := i21sysIn;
    
    CONST  Mmax = 1000;
    
    (* для упрощения примеров данные реализованы в глобальных переменных: *)
    
    VAR  p, s: ARRAY Mmax OF CHAR;  M, N: INTEGER;
    
    (* реализация предикатов, определенных в тексте: *)
            
    PROCEDURE R ( i: INTEGER ): BOOLEAN;  
        VAR  j: INTEGER;
    BEGIN
        (* 0 <= i < N *)
        j := 0;
        WHILE (j < M) & (p[j] = s[i+j]) DO INC(j) END;
        RETURN ~(j < M)
    END R;
    
    PROCEDURE Q ( i: INTEGER ): BOOLEAN;
        VAR  k: INTEGER;
    BEGIN
        k := 0;
        WHILE  ( k < i ) & ~R( k )  DO  INC( k )  END;
        RETURN  ~( k < i )
    END Q;
    
    PROCEDURE P ( i, j: INTEGER ): BOOLEAN;
        VAR  k: INTEGER;
    BEGIN
        k := 0;
        WHILE  ( k < j ) & ( s[ i+k ] = p[ k ] )  DO  INC( k )  END;
        RETURN  ~( k < j )
    END P;
    
    (* Ниже в двух процедурах реализованы оба варианта простого поиска из раздела:
        1) простейший -- в виде линейного поиска с использованием предиката R;
        2) через цикл Дейкстры. 
    Переменные p, s, M, N определены как глобальные, чтобы предикаты выглядели попроще, как в книге *)
    
    PROCEDURE Простейший* ( OUT r: INTEGER );
    (* Поиск образца p длины M в тексте s длины N; M <= Mmax.
        Если p найден, то r указывает его позицию в s, иначе r = -1.
        Все данные определены как глобальные переменные в начале модуля. *)
        VAR  i: INTEGER;
    BEGIN
        (*******************************************)
        i := 0;
        WHILE (i <= N-M) & ~R(i) DO INC(i) END;
        (****************************************************)
        
        IF  i <= N-M  THEN
            r := i
        ELSE
            r := -1
        END;
    END Простейший;
    
    PROCEDURE ПоДейкстре* ( OUT r: INTEGER );
    (* То же, что Простейший, но реализация с помощью цикла Дейкстры;
    *)
        VAR  i, j: INTEGER;
    BEGIN
        (* в целях иллюстрации красным вставлены проверки инварианта цикла в начале и конце каждой ветви: ***************)
        i := 0;  j := 0;
        ASSERT( P(i,j) );
        LOOP IF (i <= N-M) & (j < M) & (s[i+j] = p[j]) THEN  
            ASSERT( P(i,j) );
            INC( j );
            ASSERT( P(i,j) );
        ELSIF (i <= N-M) & (j < M) THEN
            ASSERT( P(i,j) );
            INC( i );  j := 0;
            ASSERT( P(i,j) );
        ELSE EXIT END END;
        ASSERT( P(i,j) );
        (* конец фрагмента. ***************************************************)

        (* обработка окончания цикла *)
        IF  i <= N-M  THEN
            r := i
        ELSE
            r := -1
        END;
    END ПоДейкстре;
    
    PROCEDURE Проверить*;
        VAR  r0, r1: INTEGER;
    BEGIN
        In.Open;    ASSERT( In.done );
        In.String( s ); ASSERT( In.done );
        N := LEN( s$ );
        In.String( p ); ASSERT( In.done );
        M := LEN( p$ );

        Простейший ( r0 );
        ПоДейкстре ( r1 );
        ASSERT( r0 = r1 );

        Log.Int( r0 );  Log.Ln;
    END Проверить;
    
END  ADruS191_Простой.
Теги: