#encoding: utf-8 #author: xu jin #date: Nov 12, 2012 #EditDistance #to find the minimum cost by using EditDistance algorithm #example output: #  "Please input a string: " #  exponential #  "Please input the other string: " #  polynomial #  "The expected cost is 6" #  The result is : #    ["e", "x", "p", "o", "n", "e", "n", "-", "t", "i", "a", "l"] #    ["-", "-", "p", "o", "l", "y", "n", "o", "m", "i", "a", "l"] p "Please input a string: " x = gets.chop.chars.map{|c| c} p "Please input the other string: " y = gets.chop.chars.map{|c| c} x.unshift(" ") y.unshift(" ") e = Array.new(x.size){Array.new(y.size)} flag = Array.new(x.size){Array.new(y.size)} DEL, INS, CHA, FIT = (1..4).to_a  #deleat, insert, change, and fit   def edit_distance(x, y, e, flag)   (0..x.length - 1).each{|i| e[i][0] = i}   (0..y.length - 1).each{|j| e[0][j] = j}   diff = Array.new(x.size){Array.new(y.size)}   for i in(1..x.length - 1) do     for j in(1..y.length - 1) do       diff[i][j] = (x[i] == y[j])? 0: 1       e[i][j] = [e[i-1][j] + 1, e[i][j - 1] + 1, e[i-1][j - 1] + diff[i][j]].min       if e[i][j] == e[i-1][j] + 1         flag[i][j] = DEL       elsif e[i][j] == e[i-1][j - 1] + 1         flag[i][j] = CHA       elsif e[i][j] == e[i][j - 1] + 1         flag[i][j] = INS             else flag[i][j] = FIT       end         end   end  end out_x, out_y = [], [] def solution_structure(x, y, flag, i, j, out_x, out_y)   case flag[i][j]   when FIT     out_x.unshift(x[i])     out_y.unshift(y[j])      solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)   when DEL     out_x.unshift(x[i])     out_y.unshift('-')     solution_structure(x, y, flag, i - 1, j, out_x, out_y)   when INS     out_x.unshift('-')     out_y.unshift(y[j])     solution_structure(x, y, flag, i, j - 1, out_x, out_y)   when CHA     out_x.unshift(x[i])     out_y.unshift(y[j])     solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)   end   #if flag[i][j] == nil ,go here   return if i == 0 && j == 0      if j == 0       out_y.unshift('-')       out_x.unshift(x[i])       solution_structure(x, y, flag, i - 1, j, out_x, out_y)   elsif i == 0       out_x.unshift('-')       out_y.unshift(y[j])       solution_structure(x, y, flag, i, j - 1, out_x, out_y)   end end edit_distance(x, y, e, flag) p "The expected edit distance is #{e[x.length - 1][y.length - 1]}" solution_structure(x, y, flag, x.length - 1, y.length - 1, out_x, out_y) puts "The result is : n  #{out_x}n  #{out_y}"