큐리오시티 명령 고치기

큐리오시티는 화성의 게일 분화구를 탐사하는 로버다. 최근에는 화성 토양에서 물의 흔적을 찾아냈고, 덕분에 앞으로의 유인 탐사 계획을 세우기가 한결 수월해졌다.

큐리오시티는 최대 32 Kbit/s로 지구와 직접 통신하지만, 신호가 지구와 화성 사이를 이동하는 데 평균 14분 6초가 걸린다.

로버 운전사 맷 헤벌리는 이렇게 설명한다. "돌을 보고 제동을 걸어도 로버는 이미 그 돌을 지나간 뒤입니다. 그래서 경로를 미리 짜 두고, 1미터 전진, 좌회전, 사진 촬영처럼 간단한 문자 명령을 목록으로 적어 보냅니다."

예상하지 못한 일에 아주 빠르게 대응해야 할 때도 있다. 카메라가 흥미로운 것을 잡았다면 로버의 경로를 바꿔 사진을 한 장 더 찍고 싶어진다. 이럴 때는 s/⟨문자열⟩/⟨대체 문자열⟩/g 꼴의 치환 명령을 보낸다. 이 명령은 ⟨문자열⟩이 나타나는 곳을 왼쪽부터 차례로 찾아 ⟨대체 문자열⟩로 바꾼다.

더 정확히 쓰면, $A$가 비어 있지 않은 문자열이고 $B$가 문자열일 때 문자열 $S$에 치환 명령 s/A/B/g를 적용하는 과정은 다음과 같다.

1. $S = S_L + A + S_R$를 만족하는 가장 왼쪽 $A$를 찾는다.
2. 그런 $A$가 없으면 멈춘다. 그때의 $S$가 결과다.
3. $S_R$에 s/A/B/g를 적용한 결과를 $R$라고 한다.
4. 결과는 $S_L + B + R$다.

여기서 두 가지가 따라온다.

1. $S$ 안에서 $A$가 서로 겹쳐 나타나면 왼쪽 것만 바뀐다. abababa에 s/aba/c/g를 적용하면 cbc가 된다. 첫 aba를 바꾸는 순간 문자열이 cbaba가 되고, 그 뒤로는 마지막 aba만 바꾼다.
2. 앞선 치환의 결과는 다음 치환에 쓰이지 않는다. a에 s/a/ab/g를 적용하면 ab가 되고, a에 s/a/ba/g를 적용하면 ba가 된다.

명령이 길수록 전송에도 시간이 더 걸린다. 처음 문자열을 최종 문자열로 바꾸는 치환 명령 중 가장 짧은 것을 찾아야 한다.

첫째 줄에 처음 문자열이, 둘째 줄에 최종 문자열이 주어진다. 두 문자열 모두 비어 있지 않고, 길이는 2000자를 넘지 않는다. 문자열에는 영어 알파벳, 공백, 그리고 쉼표, 콜론, 세미콜론, 하이픈 (, : ; -)만 나온다. 두 문자열은 서로 다르다.

처음 문자열을 최종 문자열로 바꾸는 치환 명령 중 가장 짧은 것의 길이를 정수 하나로 출력한다.

명령 s/A/B/g의 길이는 $|A| + |B| + 5$다. 조건을 만족하는 명령은 항상 존재한다.