23 lines
615 B
Text
23 lines
615 B
Text
100 PROGRAM "Levensht.bas"
|
|
110 LET S1$="kitten":LET S2$="sitting"
|
|
120 PRINT "The Levenshtein distance between """;S1$;""" and """;S2$;""" is:";LEVDIST(S1$,S2$)
|
|
130 DEF LEVDIST(S$,T$)
|
|
140 LET N=LEN(T$):LET M=LEN(S$)
|
|
150 NUMERIC D(0 TO M,0 TO N)
|
|
160 FOR I=0 TO M
|
|
170 LET D(I,0)=I
|
|
180 NEXT
|
|
190 FOR J=0 TO N
|
|
200 LET D(0,J)=J
|
|
210 NEXT
|
|
220 FOR J=1 TO N
|
|
230 FOR I=1 TO M
|
|
240 IF S$(I)=T$(J) THEN
|
|
250 LET D(I,J)=D(I-1,J-1)
|
|
260 ELSE
|
|
270 LET D(I,J)=MIN(D(I-1,J)+1,MIN(D(I,J-1)+1,D(I-1,J-1)+1))
|
|
280 END IF
|
|
290 NEXT
|
|
300 NEXT
|
|
310 LET LEVDIST=D(M,N)
|
|
320 END DEF
|