DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE width="15" ; 14 znakov max
DEFINE MatrixSize="225" ; 15*15

PROC Set2Dm(INT ARRAY matrix, INT x,y, val)
  matrix(x+y*width)=val
RETURN

INT FUNC Get2Dm(INT ARRAY matrix, INT x,y)
  INT res
  res=matrix(x+y*width)
RETURN(res)

INT FUNC DamerauLevenshteinDistance(STRING str1, str2)
  INT ARRAY matrix(MatrixSize)
  BYTE Result, tmp, Min, K, L, I, J, M, N

  Result=0
  M=str1(0)
  N=str2(0)

  FOR I=0 TO MatrixSize-1 DO matrix(I)=0 OD
  FOR I=0 TO M DO Set2Dm(matrix, I,1, I) OD
  FOR J=0 TO N DO Set2Dm(matrix, 1,J, J) OD
  
  FOR J=1 TO N DO
    FOR I=1 TO M DO
      IF str1(I) = str2(J) THEN
        tmp=Get2Dm(matrix, I-1, J-1)
        Set2Dm(matrix, I,J, tmp) ; no operation required
      ELSE
        Min = Get2Dm(matrix, I-1,J)+1  ; REM delete
        K = Get2Dm(matrix, I,J-1)+1    ; REM insert
        L = Get2Dm(matrix, I-1, J-1)+1 ; REM substitution
        IF K < Min THEN Min=K FI
        IF L < Min THEN Min=L FI
        Set2Dm(matrix, I,J, Min)

        ;transposition for Damerau Levenshtein Distance
        ;IF I>1 AND J>1 THEN
        ;  IF str1(I) = str2(J-1) AND str1(I-1) = str2(J) THEN
        ;    Min=Get2Dm(matrix, I,J)
        ;    tmp=Get2Dm(matrix, I-2,J-2)+1
        ;    IF Min>tmp THEN Min=tmp FI
        ;    Set2Dm(matrix, I,J, Min) ; REM transposition
        ;  FI
        ;FI

      FI
    OD
  OD
  Result=Get2Dm(matrix, M,N)
RETURN(Result)

PROC MAIN()
  INT result
  STRING Word_1(15), Word_2(15)
  PUT(125)
  PUTE()

  SCopy(Word_1,"kitten") SCopy(Word_2,"sitting")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=DamerauLevenshteinDistance(Word_1,Word_2)
  PrintF("Levenshtein Distance=%U%E%E",result)
  ;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

  SCopy(Word_1,"rosettacode") SCopy(Word_2,"raisethysword")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=DamerauLevenshteinDistance(Word_1,Word_2)
  PrintF("Levenshtein Distance=%U%E%E",result)
  ;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

  SCopy(Word_1,"qwerty") SCopy(Word_2,"qweryt")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=DamerauLevenshteinDistance(Word_1,Word_2)
  PrintF("Levenshtein Distance=%U%E%E",result)
  ;PrintF("Damerau Levenshtein Distance=%U%E%E",result)
RETURN