18 lines
823 B
Text
18 lines
823 B
Text
10 PRINT "THE LEVENSHTEIN DISTANCE..."
|
|
20 CLEAR :S$ = "KITTEN":T$ = "SITTING": GOSUB 100
|
|
30 PRINT "BETWEEN '"S$"' AND '"T$"' IS "LD
|
|
40 CLEAR :S$ = "ROSETTACODE":T$ = "RAISETHYSWORD": GOSUB 100
|
|
50 PRINT "BETWEEN '"S$"' AND '"T$"' IS "LD
|
|
60 END
|
|
|
|
REM CALCULATE LEVENSHTEIN DISTANCE (LD) GIVEN S$ T$
|
|
100 LET M = LEN (S$):N = LEN (T$): DIM D(M,N): FOR I = 0 TO M:D(I,0) = I: NEXT : FOR J = 0 TO N:D(0,J) = J: NEXT
|
|
110 FOR J = 1 TO N
|
|
120 FOR I = 1 TO M
|
|
130 IF MID$ (S$,I,1) = MID$ (T$,J,1) THEN D(I,J) = D(I - 1,J - 1): NEXT I,J:LD = D(M,N): RETURN
|
|
140 LET R = NOT (D(I,J - 1) + 1 < D(I - 1,J - 1) + 1):MIN = D(I - R,J - 1) + 1
|
|
150 LET R = MIN: IF D(I - 1,J) + 1 < MI THEN R = D(I - 1,J) + 1
|
|
160 LET D(I,J) = R
|
|
170 NEXT I,J
|
|
180 LET LD = D(M,N)
|
|
190 RETURN
|