시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 3 MB 51 13 9 23.077%

문제

Byteman은 그가 좋아하는 텍스트 에디터를 Byephone(이 이름은 단어 byte와 phone에서 따온 이름이다.) 이라는 새로운 핸드폰에 포팅하고 있다.

그 에디터의 특징 중 하나는 두 문서를 한 줄씩 비교해줄 수 있다는 것이다.

그 비교는 두 문자열의 최장 공통 부분 수열 (Longest Common Subsequence)을 계산하는 알고리즘을 기반으로 하고 있다.

Byteman은 이내 그 핸드폰이 그가 사용하는 알고리즘을 돌릴 만큼 충분한 메모리가 가지고 있지 않다는 것을 깨달았고 당신에게 도움을 요청했다.

3MB의 메모리만을 사용해서 입력으로 주어지는 두 문자열의 최장 공통 부분 수열을 구하는 프로그램을 작성해라.

입력

표준 입력의 첫번째 줄에는 두 개의 정수 n1 과 n2 (1 ≤ n1, n2 ≤ 10 000)가 주어지며, 이는 두 문자열의 길이를 의미한다.

두번째 줄과 세번째 줄에는 각각 길이가 n1,n2인 문자열이 주어지며, 두 문자열은 영어 알파벳 소문자로만 이루어져 있다.

출력

표준 출력으로 두 줄을 출력해야한다.

첫번째 줄에는 두 문자열의 최장 공통 부분 수열의 길이 K를 출력해야한다.

두번째 줄에는 길이가 K인 최장 공통 부분 수열을 출력해야한다.

만약 답이 여러개 있을 경우, 그 중에 하나만 출력한다.

예제 입력 1

5 6
abcad
dacbda

예제 출력 1

3
acd
W3sicHJvYmxlbV9pZCI6Ijc3MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJCeWVwaG9uZSIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZW1hblx1Yzc0MCBcdWFkZjhcdWFjMDAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDE0ZFx1YzJhNFx1ZDJiOCBcdWM1ZDBcdWI1MTRcdWQxMzBcdWI5N2MgQnllcGhvbmUoXHVjNzc0IFx1Yzc3NFx1Yjk4NFx1Yzc0MCZuYnNwO1x1YjJlOFx1YzViNCZuYnNwO2J5dGVcdWM2NDAgcGhvbmVcdWM1ZDBcdWMxMWMgXHViNTMwXHVjNjI4IFx1Yzc3NFx1Yjk4NFx1Yzc3NFx1YjJlNC4pJm5ic3A7XHVjNzc0XHViNzdjXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQ1NzhcdWI0ZGNcdWQzZjBcdWM1ZDAgXHVkM2VjXHVkMzA1XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YzVkMFx1YjUxNFx1ZDEzMFx1Yzc1OCBcdWQyYjlcdWM5ZDUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWI0NTAgXHViYjM4XHVjMTFjXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1MjkgXHViZTQ0XHVhZDUwXHVkNTc0XHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViZTQ0XHVhZDUwXHViMjk0IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjN2E1IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IChMb25nZXN0IENvbW1vbiBTdWJzZXF1ZW5jZSlcdWM3NDQmbmJzcDtcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YWUzMFx1YmMxOFx1YzczY1x1Yjg1YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5CeXRlbWFuXHVjNzQwIFx1Yzc3NFx1YjBiNCBcdWFkZjggXHVkNTc4XHViNGRjXHVkM2YwXHVjNzc0IFx1YWRmOFx1YWMwMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YjNjY1x1YjliNCBcdWI5Y2NcdWQwN2MgXHVjZGE5XHViZDg0XHVkNTVjIFx1YmE1NFx1YmFhOFx1YjlhY1x1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTY4XHViMmVjXHVjNTU4XHVhY2UwIFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWIzYzRcdWM2YzBcdWM3NDQgXHVjNjk0XHVjY2FkXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4zTUJcdWM3NTggXHViYTU0XHViYWE4XHViOWFjXHViOWNjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjN2E1IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTc0XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjgmbmJzcDtcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggbjEgXHVhY2ZjIG4yICgxICZsZTsgbjEsIG4yICZsZTsgMTAgMDAwKVx1YWMwMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YWNmYyBcdWMxMzhcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWFlMzhcdWM3NzRcdWFjMDAgbjEsbjJcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM2MDFcdWM1YjQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWM3YTUgXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IEtcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBLXHVjNzc4IFx1Y2Q1Y1x1YzdhNSBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWFjYmRcdWM2YjAsIFx1YWRmOCBcdWM5MTFcdWM1ZDAgXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NzI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnllcGhvbmUiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVtYW4gaXMgcG9ydGluZyBoaXMgZmF2b3VyaXRlIHRleHQgZWRpdG9yIHRvIGEgbmV3IHBob25lIGNhbGxlZCB0aGUgQnllcGhvbmUgKHRoZSBuYW1lIGNvbWVzIGZyb20gd29yZHMgYnl0ZSBhbmQgcGhvbmUpLiBPbmUgb2YgdGhlIGZlYXR1cmVzIG9mIHRoZSBlZGl0b3IgaXMgdGhlIGFiaWxpdHkgdG8gY29tcGFyZSB0d28gZG9jdW1lbnRzIGxpbmUgYnkgbGluZS4gVGhlIGNvbXBhcmlzb24gaXMgYmFzZWQgb24gYW4gYWxnb3JpdGhtIHRoYXQgY29tcHV0ZXMgdGhlIGxvbmdlc3QgY29tbW9uIHN1YnNlcXVlbmNlIG9mIHR3byBzdHJpbmdzLjxcL3A+XHJcblxyXG48cD5CeXRlbWFuIGhhcyBzb29uIHJlYWxpemVkIHRoYXQgdGhlIHBob25lIGRvZXMgbm90IGhhdmUgZW5vdWdoIG1lbW9yeSB0byBydW4gdGhlIGFsZ29yaXRobSBoZSBoYWQgaW1wbGVtZW50ZWQgYW5kIGhlIGFza2VkIHlvdSBmb3IgaGVscC4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoZSBsb25nZXN0IGNvbW1vbiBzdWJzZXF1ZW5jZSBvZiB0d28gaW5wdXQgc3RyaW5ncyB1c2luZyBvbmx5IHRocmVlIG1lZ2FieXRlcyBvZiBtZW1vcnkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4xIGFuZCBuMiAoMSAmbGU7IG4xLCBuMiAmbGU7IDEwIDAwMCksIGRlbm90aW5nIHRoZSBsZW5ndGhzIG9mIHRoZSBpbnB1dCBzdHJpbmdzLiBUaGUgc2Vjb25kIGFuZCB0aGUgdGhpcmQgbGluZSBjb250YWluIHN0cmluZ3Mgb2YgbGVuZ3RocyBuMSBhbmQgbjIgcmVzcGVjdGl2ZWx5LCB3aGljaCBjb25zaXN0IG9ubHkgb2YgbG93ZXJjYXNlIGxldHRlcnMgb2YgRW5nbGlzaCBhbHBoYWJldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdHdvIGxpbmVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuIFRoZSBmaXJzdCBsaW5lIHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIGsgZXF1YWwgdG8gdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBjb21tb24gc3Vic2VxdWVuY2Ugb2YgdGhlIGlucHV0IHdvcmRzLiBJbiB0aGUgc2Vjb25kIGxpbmUsIHRoZXJlIHNob3VsZCBiZSBhIGsgY2hhcmFjdGVyIGxvbmcgc3RyaW5nIGRlc2NyaWJpbmcgdGhlIGNvbW1vbiBzdWJzZXF1ZW5jZS4gSWYgdGhlcmUgYXJlIG1hbnkgb3B0aW1hbCByZXN1bHRzLCB5b3VyIHByb2dyYW0gbWF5IG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Camp > Czech, Polish and Slovak Preparation Camp > CPSPC 2010 41번