레벤슈타인 거리
Problem
텍스트 문자열이 주어집니다. 이를 사용하여 다음 작업을 수행할 수 있습니다.
<사업부>1. 문자열의 한 문자를 다른 문자로 바꿉니다.
<사업부>2. 임의의 문자 하나를 삭제합니다.
<사업부>3. 문자열의 임의의 위치에 임의의 문자를 삽입합니다.
예를 들어 "JUICE" 문자열의 첫 번째 연산을 사용하면 다음과 같습니다. 문자열 "SUK"는 두 번째 작업인 문자열 "OK"를 사용하고 세 번째 작업인 문자열 "STOCK"을 사용할 수 있습니다.
한 문자열에서 다른 문자열을 얻는 데 사용할 수 있는 이러한 작업의 최소 수를 편집 비용 또는 Levenshtein 거리라고 합니다.
주어진 두 문자열에 대한 Levenshtein 거리를 찾으십시오.
입력
프로그램은 입력으로 두 개의 문자열을 수신하며 각 문자열의 길이는 1000자를 초과하지 않으며 문자열은 대문자 라틴 문자로만 구성됩니다.
출력
단일 숫자 출력에 필요 – 주어진 문자열에 대한 Levenshtein 거리.
<몸>
| 입력 |
출력 |
|
ABCDEFGH
ACDEXGIH
|
3 |