28 lines
845 B
Text
28 lines
845 B
Text
PRINT "'kitten' -> 'sitting' has distance " ;
|
|
PRINT ; FNlevenshtein("kitten", "sitting")
|
|
PRINT "'rosettacode' -> 'raisethysword' has distance " ;
|
|
PRINT ; FNlevenshtein("rosettacode", "raisethysword")
|
|
END
|
|
|
|
DEF FNlevenshtein(s$, t$)
|
|
LOCAL i%, j%, m%, d%()
|
|
DIM d%(LENs$, LENt$)
|
|
FOR i% = 0 TO DIM(d%(),1)
|
|
d%(i%,0) = i%
|
|
NEXT
|
|
FOR j% = 0 TO DIM(d%(),2)
|
|
d%(0,j%) = j%
|
|
NEXT
|
|
FOR j% = 1 TO DIM(d%(),2)
|
|
FOR i% = 1 TO DIM(d%(),1)
|
|
IF MID$(s$,i%,1) = MID$(t$,j%,1) THEN
|
|
d%(i%,j%) = d%(i%-1,j%-1)
|
|
ELSE
|
|
m% = d%(i%-1,j%-1)
|
|
IF d%(i%,j%-1) < m% m% = d%(i%,j%-1)
|
|
IF d%(i%-1,j%) < m% m% = d%(i%-1,j%)
|
|
d%(i%,j%) = m% + 1
|
|
ENDIF
|
|
NEXT
|
|
NEXT j%
|
|
= d%(i%-1,j%-1)
|