Minimum Edit Distance Conversion

You are given two strings S and T. Your task is to compute the minimum number of operations required to convert string S into string T using the following operations:

• Insert a character
• Delete a character
• Replace a character

The solution involves dynamic programming. In particular, define a 2D table \(dp\) where \(dp[i][j]\) is the minimum number of steps to convert the first \(i\) characters of S to the first \(j\) characters of T. The recurrence relation is given by:

\(dp[i][j] = \min \Big( dp[i-1][j-1] + \mathbb{1}(S[i] \neq T[j]),\; dp[i-1][j] + 1,\; dp[i][j-1] + 1 \Big)\)

where \(\mathbb{1}(S[i] \neq T[j])\) is 0 if \(S[i] = T[j]\) and 1 otherwise. Your program should read the source string and target string from standard input and output the computed minimum edit distance.

inputFormat

The input consists of two lines:

1. The first line contains the source string S.
2. The second line contains the target string T.

outputFormat

Output a single integer which denotes the minimum number of operations required to convert S to T. The permitted operations are insertion, deletion, or substitution of a character.

## sample

horse
ros

3

</p>