Minimum Edit Distance

Given two strings S and T, compute the minimum number of operations required to transform S into T. The allowed operations are insertion, deletion, and substitution of a single character. Mathematically, if we denote the cost of transforming S into T as ( D(S,T) ), then: [ D(S,T) = \min\begin{cases} D(S_{1..(n-1)}, T) + 1, \ D(S, T_{1..(m-1)}) + 1, \ D(S_{1..(n-1)}, T_{1..(m-1)}) + \delta(S_n, T_m) \end{cases} ] where ( \delta(S_n, T_m) = 0 ) if ( S_n = T_m ) and 1 otherwise. The solution should use dynamic programming to fill a table of size ( (n+1) \times (m+1) ).

inputFormat

Input is given via stdin. The first line contains the string S and the second line contains the string T. Both strings can consist of lowercase and uppercase letters.

outputFormat

Output to stdout a single integer representing the minimum number of operations required to transform S into T.## sample

kitten
sitting

3