(*
* https://en.wikipedia.org/wiki/Levenshtein_distance
*)

let levenshteinDistance source target =
    let sourceLen = String.length source
    let targetLen = String.length target
    let distance = Array2D.zeroCreate<int> (sourceLen + 1) (targetLen + 1)
    Array2D.iteri (fun i _ _ -> distance.[i,0] <- i) distance |> ignore
    Array2D.iteri (fun _ j _ -> distance.[0,j] <- j) distance |> ignore
    for i in 1..sourceLen do
         for j in 1..targetLen do
            let cost = if target.[j - 1] = source.[i - 1] then 0
                       else 1
            distance.[i,j] <- min (min (distance.[i - 1, j] + 1) (distance.[i, j - 1] + 1))
                                  distance.[i - 1, j - 1] + cost
    distance.[sourceLen, targetLen]

let similarity source target =
    let dist = levenshteinDistance source target
    (1.0 - (float dist / float (max source.Length target.Length))) * 100.0

let reportSimilarity str1 str2 =
    sprintf "'%s' is similar to '%s' for %.2f%%" str1 str2 (similarity str1 str2)

let tests =
    sprintf "%s\n%s\n%s\n" 
                (reportSimilarity "test" "test")
                (reportSimilarity "first" "second")
                (reportSimilarity "another" "this")