(* ------------------------------------------------------------------------
  :Program.       WLD
  :Contents.      Berechnung der gewichteten Levenshtein-Distanz
  :Author.        Ludwig Geromiller
  :Address.       Filderstraße 63
  :Address.       D7000 Stuttgart 1
  :History.       v1.0  Ludwig Geromiller  sometimes  initial
  :Copyright.     Public Domain
  :Language.      Modula-2
  :Translator.    M2Amiga 3.3d
  :Remark.        Siehe auch c't 7/89
------------------------------------------------------------------------ *)
MODULE WLD;

FROM Terminal IMPORT WriteLn, Write, WriteString;
FROM InOut    IMPORT ReadString, WriteInt;
FROM Strings  IMPORT Length;

CONST
  wmax = 40;
  p    = 1;
  q    = 1;
  r    = 1;

VAR
  d         : ARRAY [0..wmax],[0..wmax] OF INTEGER;
  w1, w2    : ARRAY [1..wmax] OF CHAR;
  l1, l2    : INTEGER;

PROCEDURE min(x, y, z: INTEGER): INTEGER;
BEGIN
  IF x < y THEN
    y := x;
  END; (* IF *)
  IF y < z THEN
    z := y;
  END; (* IF *)
  RETURN z;
END min;

PROCEDURE pp(x, y: INTEGER): INTEGER;
BEGIN
  IF w1[x]=w2[y] THEN
    RETURN 0;
  ELSE
    RETURN p;
  END; (* IF *)
END pp;

PROCEDURE wld():LONGINT;
VAR
  i, j: INTEGER;
BEGIN
  d[0,0] := 0;
  FOR j := 1 TO wmax DO
    d[0,j] := d[0,j-1] + q;
  END; (* FOR *)
  FOR i := 1 TO wmax DO
    d[i,0] := d[i-1,0] + r;
  END; (* FOR *)
  FOR i := 1 TO l1 DO
    FOR j := 1 TO l2 DO
      d[i,j] := min ( d[i-1,j-1] + pp(i,j),
                      d[i  ,j-1] + q,
                      d[i-1,j  ] + r);
    END; (* FOR *)
  END; (* FOR *)
  RETURN LONGINT(d[l1,l2]);
END wld;

PROCEDURE display();
VAR
  i, j: INTEGER;
BEGIN
  WriteLn;
  WriteString("   |   ");
  FOR j := 1 TO l2 DO
    WriteString("  "); Write(w2[j]);
  END; (* FOR *)
  WriteLn;
  WriteString("---+---");
  FOR j := 1 TO l2 DO
    WriteString("---");
  END; (* FOR *)
  Write("-"); WriteLn;
  FOR i := 0 TO l1 DO
    IF i=0 THEN
      WriteString("  ")
    ELSE
      Write(" "); Write(w1[i])
    END; (* IF *)
    WriteString (" |");
    FOR j := 0 TO l2 DO
      WriteInt(LONGINT(d[i,j]),3);
    END; (* FOR *)
    WriteLn;
  END; (* FOR *)
END display;

BEGIN (* WLD *)
  REPEAT
    WriteLn;
    WriteString("Wort Nr. 1:  "); ReadString(w1);
    WriteString("Wort Nr. 2:  "); ReadString(w2);
    l1 := Length(w1);
    l2 := Length(w2);
    WriteLn;
    WriteString("Distanz:     "); WriteInt(wld(),3); WriteLn;
    display
  UNTIL (l1=0)OR(l2=0);

END WLD.