Minimum Edit Distance Transformation

You are given two strings: a source string src and a target string tgt. Your task is to compute the minimum number of operations required to transform the source string into the target string. The allowed operations are:

• Insertion
• Deletion
• Replacement

This problem can be solved using dynamic programming. The state transition is given by the following recurrence relation:

\( dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } src[i] = tgt[j] \\ \min\{ dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1] \} + 1 & \text{otherwise} \end{cases} \)

Input is read from stdin and output is written to stdout.

inputFormat

The input consists of two lines:

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

outputFormat

Output a single integer representing the minimum number of operations required to transform src into tgt.

## sample

kitten
sitting

3

</p>