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[j-1] == str2[i-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")