www.pudn.com > dpa.rar > uDpa.pas

unit uDpa; 
 
interface 
 
uses 
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, 
  Dialogs, StdCtrls, Grids; 
 
type 
  TForm1 = class(TForm) 
    StringGrid1: TStringGrid; 
    Edit1: TEdit; 
    Edit2: TEdit; 
    Button1: TButton; 
    Memo1: TMemo; 
    procedure Button1Click(Sender: TObject); 
  private 
    procedure TraceBack(const row1, row2, row3: string; i, j: Integer); 
    { Private declarations } 
  public 
    { Public declarations } 
  end; 
 
var 
  Form1: TForm1; 
 
implementation 
 
{$R *.dfm} 
 
procedure TForm1.TraceBack(const row1, row2, row3: string; i, j: Integer); 
// recover the alignment of s1 and s2 
var 
  diag: integer; 
  diagCh: char; 
begin 
   if (i > 1) and (j > 1) then 
   begin 
      diag := strtoint(StringGrid1.cells[j-1,i-1]); 
      diagCh := '|'; 
      if StringGrid1.cells[j,0]<>StringGrid1.cells[0,i] then 
      begin 
        inc(diag); diagCh := ' '; 
      end; 
 
      if strtoint(StringGrid1.cells[j,i]) = diag  then//LAllison comp sci monash uni au 
         traceBack(StringGrid1.cells[0,i]+row1, diagCh+row2, StringGrid1.cells[j,0]+row3, i-1, j-1)    // change or match 
      else if strtoint(StringGrid1.cells[j,i]) = strtoint(StringGrid1.cells[j,i-1]) + 1 then // delete 
         traceBack(StringGrid1.cells[0,i]+row1, ' '+row2, '-'+row3, i-1, j) 
      else 
         traceBack('-'+row1, ' '+row2, StringGrid1.cells[j,0]+row3, i, j-1);      // insertion 
   end 
   else if(i > 1) then 
      traceBack(StringGrid1.cells[0,i]+row1, ' '+row2, '-'+row3, i-1, j) 
   else if(j > 1) then 
      traceBack('-'+row1, ' '+row2, StringGrid1.cells[j, 0]+row3, i, j-1) 
   else // i==0 and j==0 
      memo1.Lines.Text := row1+#13#10+row2+#13#10+row3+#13#10; 
end;//traceBack 
 
procedure TForm1.Button1Click(Sender: TObject); 
var 
  i,j,k, v1, v2, v3: integer; 
begin 
  if (edit1.text='') or (edit2.Text='') then exit; 
  StringGrid1.RowCount := length(edit1.text)+2; 
  StringGrid1.ColCount := length(edit2.text)+2; 
  for I := 1 to StringGrid1.ColCount-1 do    // Iterate 
  begin 
    StringGrid1.Cells[i+1, 0]:=edit2.Text[i]; 
    StringGrid1.Cells[i, 1]:=inttostr(i-1); 
  end;    // for 
  for I := 1 to StringGrid1.RowCount-1 do    // Iterate 
  begin 
    StringGrid1.Cells[0, i+1]:=edit1.Text[i]; 
    StringGrid1.Cells[1, i]:=inttostr(i-1); 
  end;    // for 
 
  for I := 2 to StringGrid1.RowCount - 1 do    // Iterate 
  begin 
    for j := 2 to StringGrid1.ColCount - 1 do    // Iterate 
    begin 
      v1 := strtoint(StringGrid1.Cells[j-1,i-1]); 
      if StringGrid1.Cells[j,0]<>StringGrid1.Cells[0,i] then 
        inc(v1); 
      v2 := strtoint(StringGrid1.Cells[j-1,i])+1; 
      v3 := strtoint(StringGrid1.Cells[j,i-1])+1; 
      if (v1<=v2) and (v1<=v3) then 
        v3:=v1 
      else if (v2<=v1) and (v2<=v3) then 
        v3:=v2; 
      StringGrid1.Cells[j,i]:=inttostr(v3); 
    end;    // for 
  end;    // for 
  TraceBack('','','', StringGrid1.RowCount-1, StringGrid1.ColCount-1); 
  memo1.Lines.Add(format('edit-distance=%s',[ 
    StringGrid1.Cells[StringGrid1.ColCount-1,StringGrid1.RowCount-1]])); 
end; 
 
end.