unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Button1: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    procedure FormShow(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
 Form1 : TForm1;

implementation

{$R *.dfm}

var
 FiR0 : integer;
 FiP0 : integer;
 FiQ0 : integer;

procedure LevenshteinPQR(p,q,r:integer);
begin
  FiP0 := p;
  FiQ0 := q;
  FiR0 := r;
end;

function LevenshteinDistance(const sString,sPattern: String): Integer;
const
  MAX_SIZE = 50;
var
  aiDistance: array [0..MAX_SIZE,0..MAX_SIZE] of Integer;
  i,j,
  iP,iQ,iR,iPP,
  iStringLength,
  iPatternLength,
  iMaxI,iMaxJ    : Integer;
  chChar         : Char;

  function Min(X,Y,Z: Integer): Integer;
  begin
    if (X<Y) then
      Result:=X
    else
      Result:=Y;
    if (Result>Z) then
      Result:=Z;
  end; {Min}

begin
  iStringLength:=length(sString);
  if (iStringLength>MAX_SIZE) then
    iMaxI:=MAX_SIZE
  else
    iMaxI:=iStringLength;
  iPatternLength:=length(sPattern);
  if (iPatternLength>MAX_SIZE) then
    iMaxJ:=MAX_SIZE
  else
    iMaxJ:=iPatternLength;

  aiDistance[0, 0]:=0;
  for i:=1 to iMaxI do
    aiDistance[i, 0]:=aiDistance[i-1, 0]+FiR0;
  for j:=1 to iMaxJ do begin
    chChar:=sPattern[j];
    if ((chChar='*') or (chChar='?')) then
      iP:=0
    else
      iP:=FiP0;
    if (chChar='*') then
      iQ:=0
    else
      iQ:=FiQ0;
    if (chChar='*') then
      iR:=0
    else
      iR:=FiR0;

    aiDistance[0, j]:=aiDistance[0, j-1]+iQ;

    for i:=1 to iMaxI do begin
      if (sString[i]=sPattern[j]) then
        iPP:=0
      else
        iPP:=iP;
      {*** aiDistance[i,j] := Minimum of 3 values ***}
      aiDistance[i,j]:=Min(aiDistance[i-1, j-1]+iPP,
                           aiDistance[i, j-1]  +iQ,
                           aiDistance[i-1, j]  +iR);
    end;
  end;
  Result:=aiDistance[iMaxI, iMaxJ];
end; {Andreas Schmidt}

procedure TForm1.FormShow(Sender: TObject);
begin
  LevenshteinPQR(1, 1, 1);
end;

procedure TForm1.Button1Click(Sender: TObject);
var ADist : integer;
begin
  ADist:=LevenshteinDistance(Edit1.Text, Edit2.Text);
  Label1.Caption:=IntToStr(ADist);
end;

end.