문자열 컴퓨터

문자열을 처리하는 컴퓨터 X9091은 입력 문자열을 목표 문자열로 변환한다. 이 컴퓨터의 명령어 집합에는 다음 세 가지 변환 명령만 있으며, 각 명령은 실행되는 순간 메모리에 들어 있는 문자열을 바꾼다.

• 삭제(Delete): 지정한 위치의 문자를 지운다.
• 삽입(Insert): 지정한 위치에 문자를 끼워 넣는다.
• 변경(Change): 지정한 위치의 문자를 다른 문자로 바꾼다.

각 명령은 ZXdd 형식으로 쓴다. 여기서 Z는 명령 코드(D, I, C), X는 문자, dd는 두 자리 위치 번호다. 프로그램은 정지 명령 E로 끝난다. 각 명령은 실행되는 순간의 문자열에 대해 동작한다.

예를 들어 문자열 abcde는 다음 프로그램으로 bcgfe로 바꿀 수 있다(위치는 1부터 센다).

     abcde
Da01 bcde    위치 1의 'a'를 삭제
Cg03 bcge    위치 3을 'g'로 변경
If04 bcgfe   위치 4에 'f'를 삽입
E    bcgfe   정지

이 프로그램은 변환 명령을 세 개 사용하며(정지 명령 E는 세지 않는다), 이 두 문자열에 대해 더 짧은 프로그램은 없다.

입력 문자열과 목표 문자열이 주어질 때, 입력 문자열을 목표 문자열로 바꾸는 데 필요한 변환 명령(삭제, 삽입, 변경)의 최소 개수를 구하라.

입력은 여러 줄로 이루어진다. 각 줄에는 정확히 하나의 공백으로 구분된 두 문자열, 즉 입력 문자열과 목표 문자열이 순서대로 주어진다. 각 문자열은 최대 20개의 소문자로 이루어진다. 입력은 # 한 글자만 있는 줄로 끝난다.

각 입력 줄마다 한 줄에, 입력 문자열을 목표 문자열로 바꾸는 데 필요한 변환 명령(삭제, 삽입, 변경)의 최소 개수를 출력한다.