시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4Jm5ic3A7XHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IG4xIFx1YWNmYyBuMiAoMSAmbGU7IG4xLCBuMiAmbGU7IDEwIDAwMClcdWFjMDAmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NFx1YjI5NCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVhY2ZjIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWFlMzhcdWM3NzRcdWFjMDAgbjEsbjJcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM2MDFcdWM1YjQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjN2E1IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBLXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIEtcdWM3NzggXHVjZDVjXHVjN2E1IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YWNiZFx1YzZiMCwgXHVhZGY4IFx1YzkxMVx1YzVkMCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc3MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCeWVwaG9uZSIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZW1hbiBpcyBwb3J0aW5nIGhpcyBmYXZvdXJpdGUgdGV4dCBlZGl0b3IgdG8gYSBuZXcgcGhvbmUgY2FsbGVkIHRoZSBCeWVwaG9uZSAodGhlIG5hbWUgY29tZXMgZnJvbSB3b3JkcyBieXRlIGFuZCBwaG9uZSkuIE9uZSBvZiB0aGUgZmVhdHVyZXMgb2YgdGhlIGVkaXRvciBpcyB0aGUgYWJpbGl0eSB0byBjb21wYXJlIHR3byBkb2N1bWVudHMgbGluZSBieSBsaW5lLiBUaGUgY29tcGFyaXNvbiBpcyBiYXNlZCBvbiBhbiBhbGdvcml0aG0gdGhhdCBjb21wdXRlcyB0aGUgbG9uZ2VzdCBjb21tb24gc3Vic2VxdWVuY2Ugb2YgdHdvIHN0cmluZ3MuPFwvcD5cclxuXHJcbjxwPkJ5dGVtYW4gaGFzIHNvb24gcmVhbGl6ZWQgdGhhdCB0aGUgcGhvbmUgZG9lcyBub3QgaGF2ZSBlbm91Z2ggbWVtb3J5IHRvIHJ1biB0aGUgYWxnb3JpdGhtIGhlIGhhZCBpbXBsZW1lbnRlZCBhbmQgaGUgYXNrZWQgeW91IGZvciBoZWxwLiBXcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIGxvbmdlc3QgY29tbW9uIHN1YnNlcXVlbmNlIG9mIHR3byBpbnB1dCBzdHJpbmdzIHVzaW5nIG9ubHkgdGhyZWUgbWVnYWJ5dGVzIG9mIG1lbW9yeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbjEgYW5kIG4yICgxICZsZTsgbjEsIG4yICZsZTsgMTAgMDAwKSwgZGVub3RpbmcgdGhlIGxlbmd0aHMgb2YgdGhlIGlucHV0IHN0cmluZ3MuIFRoZSBzZWNvbmQgYW5kIHRoZSB0aGlyZCBsaW5lIGNvbnRhaW4gc3RyaW5ncyBvZiBsZW5ndGhzIG4xIGFuZCBuMiByZXNwZWN0aXZlbHksIHdoaWNoIGNvbnNpc3Qgb25seSBvZiBsb3dlcmNhc2UgbGV0dGVycyBvZiBFbmdsaXNoIGFscGhhYmV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0d28gbGluZXMgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC4gVGhlIGZpcnN0IGxpbmUgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgayBlcXVhbCB0byB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGNvbW1vbiBzdWJzZXF1ZW5jZSBvZiB0aGUgaW5wdXQgd29yZHMuIEluIHRoZSBzZWNvbmQgbGluZSwgdGhlcmUgc2hvdWxkIGJlIGEgayBjaGFyYWN0ZXIgbG9uZyBzdHJpbmcgZGVzY3JpYmluZyB0aGUgY29tbW9uIHN1YnNlcXVlbmNlLiBJZiB0aGVyZSBhcmUgbWFueSBvcHRpbWFsIHJlc3VsdHMsIHlvdXIgcHJvZ3JhbSBtYXkgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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