33 lines
802 B
Text
33 lines
802 B
Text
10 REM Levenshtein distance
|
|
20 ML=20:REM Max. length
|
|
30 DIM D(ML,ML)
|
|
40 PRINT "The Levenshtein distance..."
|
|
50 S$="kitten":T$="sitting"
|
|
60 GOSUB 1000
|
|
70 PRINT "between '";S$;"' and '";T$;"' is";DS
|
|
80 S$="rosettacode":T$="raisethysword"
|
|
90 GOSUB 1000
|
|
100 PRINT "between '";S$;"' and '";T$;"' is";DS
|
|
110 END
|
|
1000 REM ** Calculate dist. for S$ and T$
|
|
1010 M=LEN(S$):N=LEN(T$)
|
|
1020 FOR I=0 TO M
|
|
1030 D(I,0)=I
|
|
1040 NEXT I
|
|
1050 FOR J=0 TO N
|
|
1060 D(0,J)=J
|
|
1070 NEXT J
|
|
1080 FOR J=1 TO N
|
|
1090 FOR I=1 TO M
|
|
1100 IF MID$(S$,I,1)<>MID$(T$,J,1) THEN 1120
|
|
1110 D(I,J)=D(I-1,J-1):GOTO 1180
|
|
1120 IF D(I,J-1)+1<D(I-1,J-1)+1 THEN 1140
|
|
1130 MIN=D(I-1,J-1)+1:GOTO 1150
|
|
1140 MIN=D(I,J-1)+1
|
|
1150 IF D(I-1,J)+1<MIN THEN 1170
|
|
1160 D(I,J)=MIN:GOTO 1180
|
|
1170 D(I,J)=D(I-1,J)+1
|
|
1180 NEXT I
|
|
1190 NEXT J
|
|
1200 DS=D(M,N)
|
|
1210 RETURN
|