(* | |

* 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() |

Please leave a comment if you have any question or suggestion. Thanks!

# More on Edit Distance

[1] Section 5.5 of Algorithm Lecture note by Jeff Erickson

[2] Dynamic Programming Algorithm for Edit-Distance

[3] Edit Distance from Algorithmist

[4] Blog post by Dave Fancher.

## 2 thoughts on “SPOJ 6219. Edit Distance (EDIST) with F#”