let rec lev s1 s2 i j =
  if i = 0 then j
  else if j = 0 then i
  else if s1.[i - 1] = s2.[j - 1] then
    lev s1 s2 (i - 1) (j - 1)
  else
    1 + min (lev s1 s2 (i - 1) j)
            (min (lev s1 s2 i (j - 1)) (lev s1 s2 (i - 1) (j - 1)))

let dist s1 s2 = lev s1 s2 (String.length s1) (String.length s2)

;;

dist "abc" "abx"
+ dist "ab" "ba"
+ dist "abc" "axyc"
+ dist "" "abcd"
+ dist "ab" ""
