35 lines
1.4 KiB
Text
35 lines
1.4 KiB
Text
10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21)
|
|
11 CLS
|
|
20 Word_1$="kitten" : Word_2$="sitting" : ? Word_1$;" - ";Word_2$ : EXEC _DLD_ : ?
|
|
30 Word_1$="rosettacode" : Word_2$="raisethysword" : ? Word_1$;" - ";Word_2$ : EXEC _DLD_ : ?
|
|
|
|
11000 END
|
|
11600 REM DamerauLevenshteinDistance INPUT(Word_1$, Word_2$, DLDm[]) USE(I, J, K, L, M, N, Min) RETURN(INT Result)
|
|
11600 PROC _DLD_
|
|
11610 Result=0 : M=LEN(Word_1$) : N=LEN(Word_2$)
|
|
11620 FOR I=0 TO M : DLDm(I,0)=I : NEXT I
|
|
11630 FOR J=0 TO N : DLDm(0,J)=J : NEXT J
|
|
11640 FOR J=1 TO N
|
|
11650 FOR I=1 TO M
|
|
11660 IF Word_1$(I,I) = Word_2$(J,J)
|
|
11670 DLDm(I,J) = DLDm(I-1, J-1) : REM no operation required
|
|
11680 ELSE
|
|
11690 Min = DLDm(I-1, J)+1 : REM delete
|
|
11700 K = DLDm(I, J-1)+1 : REM insert
|
|
11710 L = DLDm(I-1, J-1)+1 : REM substitution
|
|
11720 IF K < Min THEN Min=K
|
|
11730 IF L < Min THEN Min=L
|
|
11740 DLDm(I,J) = Min
|
|
11750 REM IF I>1 AND J>1
|
|
11760 REM IF Word_1$(I,I) = Word_2$(J-1,J-1) AND Word_1$(I-1,I-1) = Word_2$(J,J)
|
|
11770 REM Min=DLDm(I,J) : IF Min>(DLDm(I-2,J-2)+1) THEN Min=(DLDm(I-2,J-2)+1)
|
|
11780 REM DLDm(I,J) = Min : REM transposition
|
|
11790 REM ENDIF
|
|
11800 REM ENDIF
|
|
11810 ENDIF
|
|
11820 NEXT I
|
|
11830 NEXT J
|
|
11840 Result=DLDm(M,N)
|
|
11845 REM ? "Damerau Levenshtein Distance=";Result
|
|
11846 ? "Damerau Distance=";Result
|
|
11850 ENDPROC
|