str1 = gets.chomp
str2 = gets.chomp
lenStr1 = str1.length
lenStr2 = str2.length
matrix = Array.new
(lenStr2+1).times{|i| matrix.push(Array.new(lenStr1,0))}
for i in 1..lenStr1 do
 matrix[0][i] = i
end
for i in 1..lenStr2 do
 matrix[i][0] = i
end
for i in 1..lenStr1 do
 for j in 1..lenStr2 do
  x = (str1[i-1] == str2[j-1]) ? 0 : 1
  y = matrix[j][i-1] + 1
  z = matrix[j-1][i] + 1
  matrix[j][i] = [matrix[j-1][i-1]+x,y,z].min
 end
end
print("#{matrix[lenStr2][lenStr1]}\n")