edit distance

edist.fs

(* 
 * Problem URI : http://www.spoj.com/problems/EDIST/
 * Problem Code : EDIST
 * Date        : 27.01.2013
 *)


(*
 * Algorithmic Technique
 * =======================
 * _Dynamic Programming_ with Memoization is applied to solve this problem (i.e. to 
 * compute _edit distance). First we  derive a recursive definition of Edit Distance and * afterwards, solve  the subproblems. 
 * 
 * Lets denote ``distance'' to be the function that calculates edit distance. 
 * The recursive definition can be stated as follows:   
 * 
 * Base cases: 
 * --------------
 *  distance ("","") --> 0   
 *  distance ("",s2) --> |s2|
 *  distance (s1,"") --> |s1|
 *
 * 
 *  distance (s1+ch1, s2+ch2) --> 
 *    min{ distance(s1+ch1, s2) + 1, //cost: insertion of ch2 in s1+ch1
 *         distance(s1, s2+ch2) + 1, //cost: deletion of  ch1 from s1
 *         distance(s1,s2) + (if ch1=ch2 then 0 else 1) // cost of substitution
 *       } 
 *) 
open System 

let min  ((a:int), (b:int), (c:int)) = 
  Math.Min(a, Math.Min(b,c))  

let computeEditDistance (source:string,target:string) = 
  let height,width = (source.Length, target.Length)
  let grid: int [,]  = Array2D.zeroCreate<int> (height+1) (width+1) 

  for h = 0 to height do 
    for w = 0 to width do 
      grid.[h,w] <- 
        match h,w with 
        | h,0  -> h
        | 0, w -> w
        | h, w -> 
            let s,t = source.[h-1],target.[w-1]

            let insertion = grid.[h,w-1] + 1 
            let deletion  = grid.[h-1,w] + 1
            let substitution = grid.[h-1,w-1]+(if s = t then 0 else 1) 
            min (insertion, deletion, substitution)
  grid.[height,width]

//Trivial IO Stuff 
let parseLine() = 
  let word1 = System.Console.ReadLine()
  let word2 = System.Console.ReadLine()
  word1,word2

let solveEdist() = 
  let T = System.Console.ReadLine() // Total Number of cases 
  //printfn "string cases : %s" s
  let numCases = System.Int32.Parse(T)
  //printfn "cases : %d" numCases 
  for j = 1 to numCases do 
    parseLine()
    |> computeEditDistance
    |> printfn "%d" 
solveEdist()