Distance d'édition

let levenshtein a b =
  let n = String.length a and m = String.length b in
  let mini x y = if x <= y then x else y in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 0 to n do dp.(i).(0) <- i done;     (* i suppressions *)
  for j = 0 to m do dp.(0).(j) <- j done;     (* j insertions *)
  for i = 1 to n do
    for j = 1 to m do
      let c = if a.[i - 1] = b.[j - 1] then 0 else 1 in
      dp.(i).(j) <-
        mini (mini (dp.(i - 1).(j) + 1) (dp.(i).(j - 1) + 1)) (dp.(i - 1).(j - 1) + c)
    done
  done;
  dp.(n).(m)

Les trois opérations correspondent aux trois cases voisines : suppression (i-1,j), insertion (i,j-1), substitution (i-1,j-1, gratuite si les caractères coïncident). levenshtein "chat" "chien" $=3$. Coût $\Theta (nm)$.