$s1 = gets.chomp.split('')
$s2 = gets.chomp.split('')

s1_length = $s1.length

s2_length = $s2.length

$table = Array.new(s1_length + 1).map { Array.new(s2_length + 1, 0) }

def max(a, b)
  a < b ? b : a
end

def min(a, b)
  a > b ? b : a
end

max_common = -1000

(s1_length + 1).times do |i|
  (s2_length + 1).times do |j|
    if i == 0
      $table[i][j] = j
      next
    end
    if j == 0
      $table[i][j] = i
      next
    end

    $table[i][j] = if $s1[i - 1] == $s2[j - 1]
                     $table[i - 1][j - 1]
                   else
                     min(min($table[i - 1][j], $table[i][j - 1]), $table[i - 1][j - 1]) + 1
                  end
  end
end
puts $table.last.last

