바이러스 복제
면접 대비시간 제한1초메모리 제한128 MB
한 구간을 갈아끼워 바뀐 전후 DNA 염기서열이 주어질 때 삽입된 조각의 최소 길이를 구합니다.
문제
상근이는 DNA의 일부를 교체해 복제하는 바이러스를 발견했다.
이 바이러스는 DNA에서 연속된 한 구간을 골라 다른 DNA 조각으로 교체한다.
다음 연구를 위해 바이러스가 교체한 DNA의 길이를 구하려고 한다.
감염되기 전 DNA와 감염된 후 DNA가 주어진다. 첫 번째 DNA를 두 번째 DNA로 바꾸려면 연속된 DNA 조각 하나를 삽입해야 한다. 이 조각의 길이가 될 수 있는 값 중 최솟값을 구하는 프로그램을 작성하시오.
조각을 삽입하기 전에 원래 그 자리에 있던 DNA를 제거할 수도 있다.
입력
첫째 줄에 감염되기 전 DNA, 둘째 줄에 감염된 후 DNA가 주어진다.
DNA는 A, G, C, T로만 이루어지고, 길이는 1 이상 이하이다.
출력
첫째 줄에 바이러스가 삽입한 DNA 조각 길이의 최솟값을 출력한다.