The Ada Program: approx.adb

  1 -- approx.adb:  approximate string matching
  2 
  3 function Approx (K: Natural; Pat, Text: String) return Boolean is
  4 
  5    M : constant Natural := Pat'Length; -- number of chars in pattern
  6    T : array (0..M) of Natural;
  7    Tj, Tj1: Integer;
  8 
  9 begin
 10    -- If you can have more substitutions than you have characters
 11    -- in the pattern, then any substring in the text will do.
 12    if M<=K then
 13       return True;
 14    end if;
 15 
 16    for J in 0..M loop
 17       T(J) := J;
 18    end loop;
 19 
 20    -- Search the text from the end to the beginning
 21    for I in reverse Text'Range loop
 22       Tj1 := 0;  -- Initialize T(J-1)
 23       for J in 1..M loop
 24          Tj := T(J);
 25          -- Compare the Ith character of the text with the
 26          -- Jth char from the end of the pattern
 27          if Text(I) /= Pat(Pat'Last-J+1) then
 28             Tj1 := Tj1 + 1;  -- replacement will cost 1
 29          end if;
 30 
 31          -- T(J) = Min (Tj1, Tj+1, T(J-1)+1)
 32          if Tj+1 < Tj1     then Tj1 := Tj+1;     end if;
 33          if T(J-1)+1 < Tj1 then Tj1 := T(J-1)+1; end if;
 34          T(J) := Tj1;
 35 
 36          Tj1  := Tj;
 37       end loop;
 38 
 39       -- T(M) is the number of errors needed so that the entire pattern
 40       -- (characters 1..M) matches the text (beginning at position I)
 41       if T(M) <= K then
 42          return True;
 43       end if;
 44    end loop;
 45 
 46    return False;  -- No match anywhere in the text
 47 end Approx;