시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 204 35 20 26.316%

문제

알파벳 소문자로만 이루어진 문자열이 주어진다. 부분문자열의 "등장값" 이란 그 부분문자열이 등장하는 횟수와 부분문자열의 길이를 곱한 값이다. 문자열이 주어졌을 때, 팰린드롬이면서 가장 큰 등장값을 가지는 부분문자열을 구하는 프로그램을 작성하시오.

입력

첫재 줄에 알파벳 소문자(a-z)로만 이루어진 문자열이 주어진다. 문자열의 길이는 300,000보다 작거나 같다.

출력

첫째 줄에 팰린드롬인 부분문자열 중에서 가장 큰 등장값을 출력한다.

예제 입력 1

abacaba

예제 출력 1

7

힌트

문자열 s의 길이를 |s|로 나타내자.

문자열 s1s2...s|s|의 부분문자열이란 1 ≤ i ≤ j ≤ |s|를 만족하는 비어있지 않은 문자열 sisi+1...sj이다. 문자열 그 자체도 부분문자열에 포함된다.

왼쪽부터 오른쪽 순서로 읽었을 때와 오른쪽부터 왼쪽 순서로 읽었을 때가 같은 문자열을 팰린드롬이라고 한다.

예제의 경우에는 총 7개의 팰린드롬 부분문자열이 있다. a, b, c, aba, aca, bacab, abacaba.

  • a는 총 4번 등장하기 때문에, 등장값은 4 × 1 = 4
  • b는 총 2번 등장하기 때문에, 등장값은 2 × 1 = 2
  • c는 총 1번 등장하기 때문에, 등장값은 1 × 1 = 1
  • aba는 총 2번 등장하기 때문에, 등장값은 2 × 3 = 6
  • aca는 총 1번 등장하기 때문에, 등장값은 1 × 3 = 3
  • bacab는 총 1번 등장하기 때문에, 등장값은 1 × 5 = 5
  • abacaba는 총 1번 등장하기 때문에, 등장값은 1 × 7 = 7

가장 큰 등장값을 가지는 팰린드롬 부분문자열은 abacab이고, 등장값은 7이다.

W3sicHJvYmxlbV9pZCI6IjEwMDY2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzMwXHViOWIwXHViNGRjXHViODZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggJnF1b3Q7XHViNGYxXHVjN2E1XHVhYzEyJnF1b3Q7IFx1Yzc3NFx1Yjc4MCBcdWFkZjggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWM2NDAgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFjZjFcdWQ1NWMgXHVhYzEyXHVjNzc0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHViYTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTAoYS16KVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAzMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjRmMVx1YzdhNVx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNCBzXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyB8c3xcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgczxzdWI+MTxcL3N1Yj5zPHN1Yj4yPFwvc3ViPi4uLnM8c3ViPnxzfDxcL3N1Yj5cdWM3NTggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzgwIDEgJmxlOyBpICZsZTsgaiAmbGU7IHxzfFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjQgczxzdWI+aTxcL3N1Yj5zPHN1Yj5pKzE8XC9zdWI+Li4uczxzdWI+ajxcL3N1Yj5cdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWFkZjggXHVjNzkwXHVjY2I0XHViM2M0IFx1YmQ4MFx1YmQ4NFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMjFjXHVjMTFjXHViODVjIFx1Yzc3ZFx1YzVjOFx1Yzc0NCBcdWI1NGNcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkXHViZDgwXHVkMTMwIFx1YzY3Y1x1Y2FiZCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZDFkIDdcdWFjMWNcdWM3NTggXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1YmQ4MFx1YmQ4NFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIGEsIGIsIGMsIGFiYSwgYWNhLCBiYWNhYiwgYWJhY2FiYS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hXHViMjk0IFx1Y2QxZCA0XHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjRmMVx1YzdhNVx1YWMxMlx1Yzc0MCA0ICZ0aW1lczsgMSA9IDQ8XC9saT5cclxuXHQ8bGk+Ylx1YjI5NCBcdWNkMWQgMlx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWI0ZjFcdWM3YTVcdWFjMTJcdWM3NDAgMiAmdGltZXM7IDEgPSAyPFwvbGk+XHJcblx0PGxpPmNcdWIyOTQgXHVjZDFkIDFcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQwIDEgJnRpbWVzOyAxID0gMTxcL2xpPlxyXG5cdDxsaT5hYmFcdWIyOTQgXHVjZDFkIDJcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQwIDIgJnRpbWVzOyAzID0gNjxcL2xpPlxyXG5cdDxsaT5hY2FcdWIyOTQgXHVjZDFkIDFcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQwIDEgJnRpbWVzOyAzID0gMzxcL2xpPlxyXG5cdDxsaT5iYWNhYlx1YjI5NCBcdWNkMWQgMVx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWI0ZjFcdWM3YTVcdWFjMTJcdWM3NDAgMSAmdGltZXM7IDUgPSA1PFwvbGk+XHJcblx0PGxpPmFiYWNhYmFcdWIyOTQgXHVjZDFkIDFcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQwIDEgJnRpbWVzOyA3ID0gNzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWQwNzAgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIGFiYWNhYlx1Yzc3NFx1YWNlMCwgXHViNGYxXHVjN2E1XHVhYzEyXHVjNzQwIDdcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDA2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhbGluZHJvbWVzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgc3RyaW5nIG9mIGxvd2VyLWNhc2UgTGF0aW4gbGV0dGVycy4gTGV0IHVzIGRlZmluZSBzdWJzdHJpbmcmcnNxdW87cyAmbGRxdW87b2NjdXJyZW5jZSB2YWx1ZSZyZHF1bzsgYXMgdGhlIG51bWJlciBvZiB0aGUgc3Vic3RyaW5nIG9jY3VycmVuY2VzIGluIHRoZSBzdHJpbmcgbXVsdGlwbGllZCBieSB0aGUgbGVuZ3RoIG9mIHRoZSBzdWJzdHJpbmcuIEZvciBhIGdpdmVuIHN0cmluZyBmaW5kIHRoZSBsYXJnZXN0IG9jY3VycmVuY2UgdmFsdWUgb2YgcGFsaW5kcm9taWMgc3Vic3RyaW5ncy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBub24tZW1wdHkgc3RyaW5nIG9mIGxvd2VyLWNhc2UgTGF0aW4gbGV0dGVycyAoYS16KS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyICZuZGFzaDsgdGhlIGxhcmdlc3Qgb2NjdXJyZW5jZSB2YWx1ZSBvZiBwYWxpbmRyb21pYyBzdWJzdHJpbmdzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD58c3wgaXMgbGVuZ3RoIG9mIHN0cmluZyBzLjxcL3A+XHJcblxyXG48cD5BIHN1YnN0cmluZyBvZiBzdHJpbmcgczxzdWI+MTxcL3N1Yj5zPHN1Yj4yPFwvc3ViPiAuIC4gLiBzPHN1Yj58c3w8XC9zdWI+IGlzIGFueSBub24tZW1wdHkgc3RyaW5nIHM8c3ViPmk8XC9zdWI+czxzdWI+aSsxPFwvc3ViPiAuIC4gLiBzPHN1Yj5qPFwvc3ViPiAsIHdoZXJlIDEgJmxlOyBpICZsZTsgaiAmbGU7IHxzfC4gQW55IHN0cmluZyBpcyBhbHNvIGl0cyBvd24gc3Vic3RyaW5nLjxcL3A+XHJcblxyXG48cD5BIHN0cmluZyBpcyBjYWxsZWQgcGFsaW5kcm9taWMsIGlmIGl0IGlzIHJlYWQgdGhlIHNhbWUgaW4gZWl0aGVyIGRpcmVjdGlvbiwgZnJvbSBsZWZ0IHRvIHJpZ2h0IGFuZCBmcm9tIHJpZ2h0IHRvIGxlZnQuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBmaXJzdCBzYW1wbGUgdGhlcmUgYXJlIHNldmVuIHBhbGluZHJvbWljIHN1YnN0cmluZ3MgYSwgYiwgYywgYWJhLCBhY2EsIGJhY2FiLCBhYmFjYWJhLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmEgaGFzIDQgb2NjdXJyZW5jZXMgaW4gdGhlIGdpdmVuIHN0cmluZywgaXRzIG9jY3VycmVuY2UgdmFsdWUgaXMgNCAmdGltZXM7IDEgPSA0PFwvbGk+XHJcblx0PGxpPmIgaGFzIDIgb2NjdXJyZW5jZXMgaW4gdGhlIGdpdmVuIHN0cmluZywgaXRzIG9jY3VycmVuY2UgdmFsdWUgaXMgMiAmdGltZXM7IDEgPSAyPFwvbGk+XHJcblx0PGxpPmMgaGFzIDEgb2NjdXJyZW5jZSBpbiB0aGUgZ2l2ZW4gc3RyaW5nLCBpdHMgb2NjdXJyZW5jZSB2YWx1ZSBpcyAxICZ0aW1lczsgMSA9IDE8XC9saT5cclxuXHQ8bGk+YWJhIGhhcyAyIG9jY3VycmVuY2VzIGluIHRoZSBnaXZlbiBzdHJpbmcsIGl0cyBvY2N1cnJlbmNlIHZhbHVlIGlzIDIgJnRpbWVzOyAzID0gNjxcL2xpPlxyXG5cdDxsaT5hY2EgaGFzIDEgb2NjdXJyZW5jZSBpbiB0aGUgZ2l2ZW4gc3RyaW5nLCBpdHMgb2NjdXJyZW5jZSB2YWx1ZSBpcyAxICZ0aW1lczsgMyA9IDM8XC9saT5cclxuXHQ8bGk+YmFjYWIgaGFzIDEgb2NjdXJyZW5jZSBpbiB0aGUgZ2l2ZW4gc3RyaW5nLCBpdHMgb2NjdXJyZW5jZSB2YWx1ZSBpcyAxICZ0aW1lczsgNSA9IDU8XC9saT5cclxuXHQ8bGk+YWJhY2FiYSBoYXMgMSBvY2N1cnJlbmNlIGluIHRoZSBnaXZlbiBzdHJpbmcsIGl0cyBvY2N1cnJlbmNlIHZhbHVlIGlzIDEgJnRpbWVzOyA3ID0gNzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNvLCB0aGUgbGFyZ2VzdCBvY2N1cnJlbmNlIHZhbHVlIG9mIHBhbGluZHJvbWljIHN1YnN0cmluZ3MgaXMgNy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2014 1번