- Time limit: 1.00 s
- Memory limit: 512 MB
The allowed operations are:
- Add one character to the string.
- Remove one character from the string.
- Replace one character in the string.
Your task is to calculate the edit distance between two strings.
Input
The first input line has a string that contains $n$ characters between A–Z.
The second input line has a string that contains $m$ characters between A–Z.
Output
Print one integer: the edit distance between the strings.
Constraints
- $1 \le n,m \le 5000$
Input:
LOVE
MOVIE
Output:
2