시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 157 46 42 29.577%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

AAAAA
AGCGAA

예제 출력 1

3

예제 입력 2

GTTTGACACACATT
GTTTGACCACAT

예제 출력 2

4
W3sicHJvYmxlbV9pZCI6IjkyNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTQgXHViY2Y1XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgRE5BXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWFkNTBcdWNjYjRcdWQ1NzQgXHViY2Y1XHVjODFjXHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYzE0XHVjNzc0XHViN2VjXHVjMmE0XHViMjk0IFx1YzViNFx1YjVhNCBETkFcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc3Y1x1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWIyZTRcdWI5NzggRE5BXHViODVjIFx1YWQ1MFx1Y2NiNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjLCBcdWIyZTRcdWM3NGMgXHVjNWYwXHVhZDZjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTRcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWQ1MFx1Y2NiNFx1YjQxYyBETkFcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxNFx1Yzc3NFx1YjdlY1x1YzJhNFx1YzVkMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWFlMzAgXHVjODA0IEROQVx1YzY0MCBcdWFjMTBcdWM1ZmNcdWI0MWMgXHVkNmM0IEROQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggRE5BXHViODVjIFx1YmMxNFx1YjAwY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjY2FiIFx1YmM4OFx1YzlmOCBETkFcdWM1ZDAgXHVjMGJkXHVjNzg1XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjBcdWMxOGRcdWI0MWMgRE5BIFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzVmMFx1YzE4ZFx1YjQxYyBETkEgXHVjODcwXHVhYzAxXHVjNzQwIFx1YzBiZFx1Yzc4NVx1YjQxOFx1YWUzMCBcdWM4MDQsIFx1YzZkMFx1Yjc5OCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBETkFcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMxNFx1Yzc3NFx1YjdlY1x1YzJhNFx1YzVkMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWFlMzAgXHVjODA0IEROQSwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMTBcdWM1ZmNcdWI0MWMgXHVkNmM0XHVjNzU4IEROQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkROQVx1YjI5NCB7QSwgRywgQywgVH1cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTA8c3VwPjU8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTRcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzBiZFx1Yzc4NVx1YjQxYyBETkEgXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTI0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZpcnVzIFJlcGxpY2F0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5Tb21lIHZpcnVzZXMgcmVwbGljYXRlIGJ5IHJlcGxhY2luZyBhIHBpZWNlIG9mIEROQSBpbiBhIGxpdmluZyBjZWxsIHdpdGggYSBwaWVjZSBvZiBETkEgdGhhdCB0aGUgdmlydXMgY2FycmllcyB3aXRoIGl0LiBUaGlzIG1ha2VzIHRoZSBjZWxsIHN0YXJ0IHRvIHByb2R1Y2UgdmlydXNlcyBpZGVudGljYWwgdG8gdGhlIG9yaWdpbmFsIG9uZSB0aGF0IGluZmVjdGVkIHRoZSBjZWxsLiBBIGdyb3VwIG9mIGJpb2xvZ2lzdHMgaXMgaW50ZXJlc3RlZCBpbiBrbm93aW5nIGhvdyBtdWNoIEROQSBhIGNlcnRhaW4gdmlydXMgaW5zZXJ0cyBpbnRvIHRoZSBob3N0IGdlbm9tZS4gVG8gXHVmYjAxbmQgdGhpcyBvdXQgdGhleSBoYXZlIHNlcXVlbmNlZCB0aGUgZnVsbCBnZW5vbWUgb2YgYSBoZWFsdGh5IGNlbGwgYXMgd2VsbCBhcyB0aGF0IG9mIGFuIGlkZW50aWNhbCBjZWxsIGluZmVjdGVkIGJ5IGEgdmlydXMuPFwvcD5cclxuXHJcbjxwPlRoZSBnZW5vbWUgdHVybmVkIG91dCB0byBiZSBwcmV0dHkgYmlnLCBzbyBub3cgdGhleSBuZWVkIHlvdXIgaGVscCBpbiB0aGUgZGF0YSBwcm9jZXNzaW5nIHN0ZXAuIEdpdmVuIHRoZSBETkEgc2VxdWVuY2UgYmVmb3JlIGFuZCBhZnRlciB0aGUgdmlydXMgaW5mZWN0aW9uLCBkZXRlcm1pbmUgdGhlIGxlbmd0aCBvZiB0aGUgc21hbGxlc3Qgc2luZ2xlLCBjb25zZWN1dGl2ZSBwaWVjZSBvZiBETkEgdGhhdCBjYW4gaGF2ZSBiZWVuIGluc2VydGVkIGludG8gdGhlIFx1ZmIwMXJzdCBzZXF1ZW5jZSB0byB0dXJuIGl0IGludG8gdGhlIHNlY29uZCBvbmUuIEEgc2luZ2xlLCBjb25zZWN1dGl2ZSBwaWVjZSBvZiBETkEgbWlnaHQgYWxzbyBoYXZlIGJlZW4gcmVtb3ZlZCBmcm9tIHRoZSBzYW1lIHBvc2l0aW9uIGluIHRoZSBzZXF1ZW5jZSBhcyBETkEgd2FzIGluc2VydGVkLiBTbWFsbCBjaGFuZ2VzIGluIHRoZSBETkEgY2FuIGhhdmUgbGFyZ2UgZWZmZWN0cywgc28gdGhlIHZpcnVzIG1pZ2h0IGluc2VydCBvbmx5IGEgZmV3IGxldHRlcnMsIG9yIGV2ZW4gbm90aGluZyBhdCBhbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgdHdvIGxpbmVzIGNvbnRhaW5pbmcgdGhlIEROQSBzZXF1ZW5jZSBiZWZvcmUgYW5kIGFmdGVyIHZpcnVzIGluZmVjdGlvbiByZXNwZWN0aXZlbHkuIEEgRE5BIHNlcXVlbmNlIGlzIGdpdmVuIGFzIGEgc3RyaW5nIGNvbnRhaW5pbmcgYmV0d2VlbiAxIGFuZCAxMDxzdXA+NTxcL3N1cD4gdXBwZXItY2FzZSBsZXR0ZXJzIGZyb20gdGhlIGFscGhhYmV0IHtBLCBHLCBDLCBUfS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIsIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiBETkEgaW5zZXJ0ZWQgYnkgdGhlIHZpcnVzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=