This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* | |
| * 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.
adilakhter λ 
2 thoughts on “SPOJ 6219. Edit Distance (EDIST) with F#”