Intuidiff

요즘 웹 애플리케이션은 글과 문서의 수정 이력을 diff 계열 도구로 비교한다. diff는 한 문서를 다른 문서로 바꾸는 삽입과 삭제를 적게 찾아내는 도구다.

여기에는 흔한 문제가 있다. 원래 문서가 두 문단 P1 P2로 이루어져 있고, 이를 고쳐서 P2 P1이 되었다고 하자. 이때 diff는 변경 내용을 P1을 지우고, P2는 그대로 두고, 새 내용을 넣었다고 설명하기도 한다. 새로 넣은 내용이 P1과 같다는 사실은 쓰이지 않는다. 그래서 diff는 어떤 의미에서 선형이고, 문서의 일부를 재배치했을 때 가장 편한 방식으로 동작하지 않는다.

더 잘할 수 있을까? (더 중요하게는, 오늘 안에 끝낼 수 있을까?) 기본 요구 사항은 이렇다. 새 문서의 어떤 부분이 이전 문서 어딘가에 이미 나왔다면, 그 사실이 드러나도록 표시해야 한다.

이 생각을 정리해 한 문서에서 다른 문서로 가는 Intuidiff 거리를 정의한다. Intuidiff 거리는 두 번째 문서를 $N$개의 조각을 이어 붙인 것으로 나타낼 수 있는 가장 작은 정수 $N$이다. 각 조각은 첫 번째 문서의 부분 문자열이거나 새로운 문자 하나다. 삭제는 신경 쓰지 않아도 된다. diff와 달리 원래 문서에서 시작하지 않고 빈 문서에서 시작하기 때문이다. 그래서 어떤 문서에서 자기 자신으로 가는 Intuidiff 거리는 1이다. 직관에 어긋나는 부분은 이것 하나뿐이다.

문자열 두 개가 주어지면 첫 번째 문자열에서 두 번째 문자열로 가는 Intuidiff 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 첫 번째 문자열이 주어진다. 둘째 줄에 두 번째 문자열이 주어진다. 두 문자열의 길이는 각각 1 이상 500 000 이하이고, 두 문자열 모두 알파벳 대소문자, 숫자, 밑줄로만 이루어져 있다.

첫째 줄에 첫 번째 문자열에서 두 번째 문자열로 가는 Intuidiff 거리를 출력한다.

첫 번째 예제에서 두 번째 문자열을 최적으로 나눈 방법 중 하나는 p + aragraph_ + e + d + i + t + 3 + _ + Paragraph이다.