Edit Distance Computation

You are given two strings: a source string and a target string. Your task is to compute the minimum number of operations required to convert the source string into the target string using the following three allowed operations:

• Insert a character
• Remove a character
• Replace a character

This problem is a classic example of computing the Edit Distance between two strings. The solution uses dynamic programming. We define the state \(dp[i][j]\) as the minimum number of operations required to convert the first \(i\) characters of the source string into the first \(j\) characters of the target string. The recurrence is given by:

\(dp[i][j] = \min\begin{cases} dp[i-1][j] + 1 \\ dp[i][j-1] + 1 \\ dp[i-1][j-1] + cost \end{cases}\)

where \(cost = 0\) if \(source[i-1] = target[j-1]\), and \(cost = 1\) otherwise.

Input is read from stdin and output should be printed to stdout.

inputFormat

The input consists of two lines:

• The first line contains the source string.
• The second line contains the target string.

outputFormat

Output a single integer representing the minimum number of operations required to convert the source string into the target string.

## sample

kitten
sitting

3