37 lines
814 B
Plaintext
37 lines
814 B
Plaintext
REM Levenshtein distance
|
|
DECLARE FUNCTION LevDist(S$, T$) AS INTEGER
|
|
DECLARE FUNCTION MIN(A, B) AS INTEGER
|
|
PRINT "The Levenshtein distance..."
|
|
PRINT "between 'kitten' and 'sitting' is "; LevDist("kitten","sitting")
|
|
PRINT "between 'rosettacode' and 'raisethysword' is "; LevDist("rosettacode","raisethysword")
|
|
END
|
|
|
|
FUNCTION LevDist(S$, T$) AS INTEGER
|
|
N = LEN(T$): M = LEN(S$)
|
|
DIM D(0 TO N, 0 TO N)
|
|
FOR I = 0 TO M
|
|
D(I, 0) = I
|
|
NEXT I
|
|
FOR J = 0 TO N
|
|
D(0, J) = J
|
|
NEXT J
|
|
FOR J = 1 TO N
|
|
FOR I = 1 TO M
|
|
IF MID$(S$, I, 1) = MID$(T$, J, 1) THEN
|
|
D(I, J) = D(I - 1, J - 1)
|
|
ELSE
|
|
D(I, J) = Min(D(I - 1, J) + 1, Min(D(I, J - 1) + 1, D(I - 1, J - 1) + 1))
|
|
END IF
|
|
NEXT I
|
|
NEXT J
|
|
LevDist = D(M, N)
|
|
END FUNCTION
|
|
|
|
FUNCTION Min(A, B) AS INTEGER
|
|
IF A < B THEN
|
|
Min = A
|
|
ELSE
|
|
Min = B
|
|
END IF
|
|
END FUNCTION
|