어떤 워드프로세서의 맞춤법 교정기는 잘못 입력된 단어 \(A\)를 사전에 있는 단어 \(B\)로 바꾸는 데 필요한 최소 편집 횟수를 계산한다. 한 번의 편집으로 할 수 있는 연산은 다음 세 가지이다.

1. 한 글자를 삽입한다.
2. 한 글자를 삭제한다.
3. 한 글자를 다른 글자로 교체한다.

각 연산의 비용은 모두 \(1\)이다. 문자열 \(A\)를 \(B\)로 만들기 위해 필요한 최소 편집 횟수(편집 거리)를 구하여라.

• \(1 \le |A|, |B| \le 2{,}000\)

첫째 줄에 문자열 \(A\)가 주어진다.

둘째 줄에 문자열 \(B\)가 주어진다.

두 문자열은 알파벳 소문자(a–z)로만 이루어진다.

\(A\)를 \(B\)로 바꾸는 최소 편집 횟수를 한 줄에 출력한다.

riseoj 작성

출처 Original