시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 107 34 31 32.292%

문제

상근이는 DNA의 일부를 교체해 복제를 시작하는 바이러스를 발견했다.

이 바이러스는 어떤 DNA의 연속된 일부분을 다른 DNA로 교체한다.

이제, 다음 연구를 위해 바이러스에 의해 교체된 DNA의 길이를 구해보려고 한다.

바이러스에 감염되기 전 DNA와 감염된 후 DNA가 주어진다. 두 번째 DNA로 바뀌기 위해 첫 번째 DNA에 삽입되어야 하는 연속된 DNA 조각의 길이를 구하는 프로그램을 작성하시오.

연속된 DNA 조각은 삽입되기 전, 원래 그 자리에 있는 DNA를 제거할 수도 있다.

입력

첫째 줄에 바이러스에 감염되기 전 DNA, 둘째 줄에 감염된 후의 DNA가 주어진다.

DNA는 {A, G, C, T}로만 이루어져 있으며, 길이는 1보다 크거나 같고, 105보다 작거나 같다.

출력

첫째 줄에 바이러스에 의해 삽입된 DNA 길이의 최소값을 출력한다.

예제 입력

AAAAA
AGCGAA

예제 출력

3

예제 입력 2

GTTTGACACACATT
GTTTGACCACAT

예제 출력 2

4

힌트