s1 = gets.chomp
s2 = gets.chomp

size1 = s1.size
size2 = s2.size
dp = Array.new(size1 + 1){Array.new(size2 + 1, 0)}
dp[0] = (0..size2).to_a
pre = 0
dp.each do |d|
  d[0] = pre
  pre += 1
end

size1.times do |i|
  size2.times do |j|
    prenum = s1[i] == s2[j] ? 0 : 1
    dp[i+1][j+1] = [dp[i+1][j] + 1, dp[i][j+1] + 1, dp[i][j] + prenum].min
  end
end
# dp.each do |d|
#   p d
# end
puts dp[size1][size2]
