29 lines
947 B
Text
29 lines
947 B
Text
100 REM Levenshtein distance
|
|
110 DECLARE EXTERNAL FUNCTION LevDist
|
|
120 PRINT "The Levenshtein distance..."
|
|
130 PRINT "between 'kitten' and 'sitting' is"; LevDist("kitten","sitting")
|
|
140 PRINT "between 'rosettacode' and 'raisethysword' is"; LevDist("rosettacode","raisethysword")
|
|
150 END
|
|
160 EXTERNAL FUNCTION LevDist(S$, T$)
|
|
170 LET N = LEN(T$)
|
|
180 LET M = LEN(S$)
|
|
190 DIM D(0 TO 20, 0 TO 20)
|
|
200 REM Both T$ and S$ must not be longer than 20 chars
|
|
210 REM Some impementations allow DIM D(0 TO M, 0 TO N), but it is not standard.
|
|
220 FOR I = 0 TO M
|
|
230 LET D(I, 0) = I
|
|
240 NEXT I
|
|
250 FOR J = 0 TO N
|
|
260 LET D(0, J) = J
|
|
270 NEXT J
|
|
280 FOR J = 1 TO N
|
|
290 FOR I = 1 TO M
|
|
300 IF S$(I:I) = T$(J:J) THEN
|
|
310 LET D(I, J) = D(I - 1, J - 1)
|
|
320 ELSE
|
|
330 LET D(I, J) = MIN(D(I - 1, J) + 1, MIN(D(I, J - 1) + 1, D(I - 1, J - 1) + 1))
|
|
340 END IF
|
|
350 NEXT I
|
|
360 NEXT J
|
|
370 LET LevDist = D(M, N)
|
|
380 END FUNCTION
|