# odleglosc Levenshteina (odleglosc edycyjna)
# www.algorytm.org
# by Paweł THZ Łuczak

def min(x1,x2,x3)
  if x1 >= x2
    if x2 >= x3
      return x3
    else
      return x2
    end
  else
    if x3 >= x1
      return x1
    else
      return x3
    end
    
  end
end

def leven(s,t)
  
  cost=0
  d = []
  m = s.length
  n = t.length
  
  
  for i in 0..m
    d[i] = []
  end
  
  for i in 0..m
    d[i][0] = i
  end
  
  for j in 1..n
    d[0][j] = j
  end
  
  for i in 1..m
    for j in 1..n
      if s[i-1,1] == t[j-1,1]
        cost = 0
      else
        cost = 1
      end
      d[i][j] = min( (d[i-1][j] + 1) , (d[i][j-1] + 1) , (d[i-1][j-1] + cost) ) 
    end
  end
  return d[m][n]
end