Module: 최대 공통 부분 수열


Problem

3 /5


Damerau-Levenshtein 거리

Problem

가장 일반적인 타이핑 오류 중 하나는 예를 들어 "프로그램"이라는 단어 대신 인접한 두 문자를 바꾸는 것입니다. "programma"라는 단어가 입력됩니다. Levenshtein 거리는 이러한 오타를 고려하지 않습니다. Levenshtein 거리를 계산할 때 하나의 순열은 두 개의 편집(예: 문자 삭제 및 삽입)으로 계산됩니다.
 
Damelau-Levenshtein 거리를 계산할 때 문자 교체, 삽입 및 삭제 작업 외에도 인접한 두 문자를 치환하는 작업도 허용됩니다. 동시에 재배열된 문자 사이에 다른 문자를 삽입할 수 없습니다.
 
주어진 두 문자열에 대한 Damerau-Levenshtein 거리를 결정합니다.
  <몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

입력 출력
XABCDE
ACBYDF
 4