Minimum Edit Distance

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\). The allowed operations are:

• Insertion
• Deletion
• Replacement

The problem can be solved using dynamic programming. One common recurrence relation is: \[ dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } s_i = t_j, \\ 1 + \min\{dp[i-1][j],\;dp[i][j-1],\;dp[i-1][j-1]\} & \text{if } s_i \neq t_j. \end{cases} \]

Implement a program that reads the input from standard input and writes the output to standard output.

inputFormat

The input consists of two lines. The first line contains the source string \(s\) and the second line contains the target string \(t\).

outputFormat

Output a single integer representing the minimum number of operations required to convert \(s\) into \(t\).

intention\nexecution

5