// Odleglosc Levenshteina (odleglosc edycyjna)
// www.algorytm.org
// (c) 2009 Tomasz Lubinski

program Levenshtein;
{$APPTYPE CONSOLE}
uses
  SysUtils;

function minimum(x1: Integer; x2: Integer; x3: Integer): Integer;
begin
   if (x1 >= x2) then
      if (x2 >= x3) then
         Result := x3
      else
         Result := x2
   else
      if (x3 >= x1) then
         Result := x1
      else
         Result := x3;
end;


function Levenshtein_d(s: String; t: String): Integer;
var
   i, j, m, n, cost: Integer;
   d: array [0..100] of array [0..100] of Integer;
begin
   m := length(s);
   n := length(t);

   for i:=0 to m do
      d[i, 0] := i;
   for j:=0 to n do
      d[0, j] := j;

   for i:=1 to m do
   begin
      for j:=1 to n do
      begin
           if s[i] = t[j] then
              cost := 0
           else
              cost := 1;

           d[i, j] := minimum(d[i-1, j] + 1,       // remove
                              d[i, j-1] + 1,       // insert
                              d[i-1, j-1] + cost)  // change
      end;
   end;

   Result := d[m, n];
end;

var
    s, t: String;
begin
    writeln('Podaj pierwszy ciag');
    readln(s);

    writeln('Podaj drug ciag');
    readln(t);

    writeln('Odleglosc Levenshteina wynosi: ' + IntToStr(Levenshtein_d(s, t)));

end.