Minimum Edit Distance

Given two strings s and t, your task is to compute the minimum number of operations required to convert s into t. The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution of one character for another

This problem is a classic example of the edit distance (also known as the Levenshtein distance) problem. The solution is commonly achieved using a dynamic programming approach. The formula used in the DP recurrence is given as:

$$ dp[i][j]=\begin{cases} i & \text{if } j=0,\\ j & \text{if } i=0,\\ 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} $$

Input is provided via standard input (stdin) and output should be printed to standard output (stdout).

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 which is the minimum number of operations required to convert string s into string t.## sample

saturday
sunday

3