s1 = gets.chomp
s2 = gets.chomp
# s1???????????°???[0..s1.size]?????£?????´???
# s2???????????°???[0..s2.size]?????£?????´???
# ??¨???????????????
res = Array.new(s1.size.succ).map{Array.new(s2.size.succ, 0)}

# ????????????????????????0???????????¨????????¢?????????????????????
for i in (0..s1.size) do
  res[i][0] = i
end
for i in (0..s2.size) do
  res[0][i] = i
end

# ??¨????????????????????????????????°??¨????????¢???1????????¨??????
# ????????§???????????°??¨????????¢???1?¢???????
# ???????????????s??¨dp???????????????1????????????
for i in (1..s1.size) do
  for j in (1..s2.size) do
    if s1[i - 1] == s2[j - 1]
      res[i][j] = res[i - 1][j - 1]
    else
      res[i][j] = [res[i - 1][j - 1], res[i - 1][j], res[i][j - 1]].min + 1
    end
  end
end
p res[s1.size][s2.size]