시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 1024 MB 90 35 13 23.214%

문제

길이가 2n인 문자열 T에 대해, T의 길이 n 접두사와 길이 n 접미사가 같을 경우 T를 제곱 문자열이라고 한다. 빈 문자열은 제곱 문자열이다.

문자열 S가 주어질 때, S의 부분 문자열이면서 제곱 문자열인 최대 길이 문자열을 출력하라. S의 부분 문자열은, S에서 몇 개의 문자를 제거하고 나머지 문자들의 순서를 바꾸지 않은 문자열을 뜻한다.

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

이후 T개의 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있다.

각 문자열의 길이는 1 이상 3000 이하이며, 주어지는 모든 문자열의 길이 합은 3000 이하이다.

출력

각 테스트 케이스에 대해서 다음과 같이 출력하라:

만약 정답이 빈 문자열이면, Case #T: 0 을 한 줄에 출력하라.

만약 정답이 빈 문자열이 아니면, Case #T: L을 첫 줄에 출력하고, 다음 줄에 정답을 출력하라.

T는 테스트 케이스의 번호 (1부터 시작)이고, L은 정답 문자열의 길이를 뜻한다.

예제 입력 1

5
abba
abbab
abac
abcd
bbabab

예제 출력 1

Case #1: 2
aa
Case #2: 4
abab
Case #3: 2
aa
Case #4: 0
Case #5: 4
bbbb
W3sicHJvYmxlbV9pZCI6IjE4NDQxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODFjXHVhY2YxIFx1YmQ4MFx1YmQ4NFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwIDJuXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNCBUXHVjNWQwIFx1YjMwMFx1ZDU3NCwgVFx1Yzc1OCBcdWFlMzhcdWM3NzQgbiBcdWM4MTFcdWI0NTBcdWMwYWNcdWM2NDAgXHVhZTM4XHVjNzc0IG4gXHVjODExXHViYmY4XHVjMGFjXHVhYzAwIFx1YWMxOVx1Yzc0NCBcdWFjYmRcdWM2YjAgVFx1Yjk3YyBcdWM4MWNcdWFjZjEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM4MWNcdWFjZjEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBTXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWJhNzRcdWMxMWMmbmJzcDtcdWM4MWNcdWFjZjEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc4IFx1Y2Q1Y1x1YjMwMCBcdWFlMzhcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gU1x1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwLCBTXHVjNWQwXHVjMTFjIFx1YmE4NyBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YWNlMCBcdWIwOThcdWJhMzhcdWM5YzAgXHViYjM4XHVjNzkwXHViNGU0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gU1x1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEgXHVjNzc0XHVjMGMxIDMwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwLCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgXHVkNTY5XHVjNzQwIDMwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yzo8XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTc0LCBDYXNlICNUOiAwIFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YmE3NCwgQ2FzZSAjVDogTFx1Yzc0NCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5UXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4ICgxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MSlcdWM3NzRcdWFjZTAsIExcdWM3NDAgXHVjODE1XHViMmY1IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NDQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3F1YXJlIFN1YnNlcXVlbmNlcyIsImRlc2NyaXB0aW9uIjoiPHA+Qm9iIGhhcyBhIHN0cmluZyBzPHN1Yj4xPFwvc3ViPnM8c3ViPjI8XC9zdWI+ICZtaWRkb3Q7ICZtaWRkb3Q7ICZtaWRkb3Q7IHM8c3ViPm48XC9zdWI+LiBIZSB3b3VsZCBsaWtlIHRvIGZpbmQgaXRzIGxvbmdlc3Qgc3Vic2VxdWVuY2UgdGhhdCBpcyBhIHNxdWFyZS4gQ291bGQgeW91IHBsZWFzZSBoZWxwIGhpbT88XC9wPlxyXG5cclxuPHA+QSBzdWJzZXF1ZW5jZSBvZiBzPHN1Yj4xPFwvc3ViPnM8c3ViPjI8XC9zdWI+ICZtaWRkb3Q7ICZtaWRkb3Q7ICZtaWRkb3Q7IHM8c3ViPm48XC9zdWI+IGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIHN0cmluZyBzPHN1Yj5wPHN1Yj4xPFwvc3ViPjxcL3N1Yj5zPHN1Yj5wPHN1Yj4yPFwvc3ViPjxcL3N1Yj4mbWlkZG90OyAmbWlkZG90OyAmbWlkZG90OyBzPHN1Yj5wPHN1Yj5tPFwvc3ViPjxcL3N1Yj4gbWVldGluZyB0aGUgY29uZGl0aW9uIHRoYXQgMSAmbGU7IHA8c3ViPjE8XC9zdWI+ICZsdDsgcDxzdWI+MjxcL3N1Yj4gJmx0OyAuIC4gLiAmbHQ7IHA8c3ViPm08XC9zdWI+ICZsZTsgbi48XC9wPlxyXG5cclxuPHA+QSBzdHJpbmcgdDxzdWI+MTxcL3N1Yj50PHN1Yj4yPFwvc3ViPiAmbWlkZG90OyAmbWlkZG90OyAmbWlkZG90O3Q8c3ViPm08XC9zdWI+IGlzIGEgc3F1YXJlIGlmIGFuZCBvbmx5IGlmOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm0gaXMgZXZlbjs8XC9saT5cclxuXHQ8bGk+dDxzdWI+aTxcL3N1Yj4gPSB0PHN1Yj5pK21cLzI8XC9zdWI+IGZvciBpID0gMSwgMiwgLiAuIC4gLCBtXC8yLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIFQgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZSBmb2xsb3dpbmcgZGVzY3JpYmVzIGFsbCB0ZXN0IGNhc2VzLiBGb3IgZWFjaCB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjxwPlRoZSBvbmx5IGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgbiBsb3dlcmNhc2UgbGV0dGVycywgczxzdWI+MTxcL3N1Yj5zPHN1Yj4yPFwvc3ViPiAmbWlkZG90OyAmbWlkZG90OyAmbWlkZG90OyBzPHN1Yj5uPFwvc3ViPi48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgVCwgbiAmbGU7IDMwMDA8XC9saT5cclxuXHQ8bGk+VGhlIHN1bSBvZiBuIGluIGFsbCB0ZXN0IGNhc2VzIGRvZXMgbm90IGV4Y2VlZCAzMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGZpcnN0bHkgb3V0cHV0IGEgbGluZSBjb250YWluaW5nICZsZHF1bztDYXNlICN4OiBtJnJkcXVvOyAod2l0aG91dCBxdW90ZXMpLCB3aGVyZSB4IGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIHN0YXJ0aW5nIGZyb20gMSwgYW5kIG0gaXMgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzcXVhcmUgc3Vic2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPklmIG0gaXMgcG9zaXRpdmUsIHRoZW4gb3V0cHV0IGEgc3RyaW5nIGluIHRoZSBuZXh0IGxpbmUsIHJlcHJlc2VudGluZyB0aGUgbG9uZ2VzdCBzcXVhcmUgc3Vic2VxdWVuY2UuIElmIHRoZXJlIGFyZSBtYW55IG9wdGltYWwgc29sdXRpb25zLCBwbGVhc2Ugb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 8 F번

  • 문제를 번역한 사람: koosaga