5319 : B20 - 편집 거리
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
문자열 $ S $ 와 $ T $ 가 주어집니다. 당신은 문자열 $ S $ 에 대해 다음 3종류의 조작을 수행할 수 있습니다.
조작 1: $ S $ 의 문자 중 하나를 선택해 삭제한다.
조작 2: $ S $ 의 문자 중 하나를 선택해 다른 문자로 변경한다.
조작 3: $ S $ 의 적당한 위치에 문자 하나를 삽입한다.
최소 몇 번의 조작으로 문자열 $ S $ 를 $ T $ 와 일치시킬 수 있습니까?
[제약 조건]
• $1 \le |S| \le 2000$
• $1 \le |T| \le 2000$
• $S, T$ 는 영소문자로 이루어진 문자열입니다.
조작 1: $ S $ 의 문자 중 하나를 선택해 삭제한다.
조작 2: $ S $ 의 문자 중 하나를 선택해 다른 문자로 변경한다.
조작 3: $ S $ 의 적당한 위치에 문자 하나를 삽입한다.
최소 몇 번의 조작으로 문자열 $ S $ 를 $ T $ 와 일치시킬 수 있습니까?
[제약 조건]
• $1 \le |S| \le 2000$
• $1 \le |T| \le 2000$
• $S, T$ 는 영소문자로 이루어진 문자열입니다.
입력 설명
첫 번째 줄에 $ S $ , 두 번째 줄에 $ T $ 가 주어집니다.
출력 설명
최소 조작 횟수를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
tokyo
kyoto
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4