Levenshtein Distance

Given two strings, compute the Levenshtein distance between them. The Levenshtein distance between two strings is defined as the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into the other. The formula can be represented in LaTeX as:

\(d(i, j) = \begin{cases} \max(i,j) & \text{if } \min(i,j)=0,\\ \min \begin{cases} d(i-1,j)+1, \\ d(i,j-1)+1, \\ d(i-1,j-1)+1_{(s_i \neq t_j)} \end{cases} & \text{otherwise.} \end{cases}\)

Your task is to implement a program that reads two lines from standard input and outputs the Levenshtein distance between them to standard output.

inputFormat

The input consists of two lines. The first line contains the first string, and the second line contains the second string.

You may assume that the strings consist only of printable characters and have a length of at most 1000.

outputFormat

Output a single integer representing the Levenshtein distance between the two input strings.

0