시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 413 110 95 42.601%

문제

어떠한 문자열에 대해서, 이 문자열을 뒤집어도 같은 문자열이 나온다 이 문자열을 팰린드롬이라 부른다. 예를 들어, "a", "aa", "appa", "queryreuq"와 같은 문자열은 모두 팰린드롬이다.

당신은 빈 문자열 S가 있을 때, 두 가지 연산을 처리해야 한다.

  1. S의 맨 뒤에 알파벳 소문자를 하나 추가한다.
  2. S의 맨 뒤에 있는 문자를 제거한다.

각각의 연산을 처리한 후, 당신은 해당 문자열에 있는 팰린드롬 부분문자열의 개수를 세어야 한다. 문자열 S와 1 ≤ ij ≤ |S|인 정수 ij에 대해서, S[i, j]를 Si번째 문자부터 j번째 문자까지를 포함하는 부분문자열 이라고 정의하자. 당신은 S[i, j]가 팰린드롬인 모든 정수쌍 (ij)의 개수를 세어서, 이를 출력하여야 한다.

입력

입력은 두개의 줄로 되어있다.

첫 번째 줄에 쿼리의 개수 Q가 주어진다.

두번재 줄에 쿼리가 길이 Q의 문자열로 주어진다. 이 중 i번째 문자 Kii번째 쿼리의 내용을 나타낸다.

Ki는 '-' 이거나, 영어 소문자 ('a', 'b', ..., 'z') 중에 하나이다. (따옴표는 제외한다.)

만약 이 문자가 '-'이라면, S의 맨 뒤의 문자를 제거해야 하며, 영어 소문자라면 S의 맨 뒤에 Ki를 삽입해야 한다.

각 쿼리를 처리한 이후 문자열의 길이가 항상 1 이상이 보장된다.    

출력

한 줄에 Q개의 정수를 하나의 공백으로 구분하여 출력한다. 이 중 i번째 정수는 i번째 쿼리에 대한 정답을 의미한다.

제한

  • 1 ≤ Q ≤ 10,000

서브태스크 1 (36점)

이 서브태스크는 다음의 조건을 만족한다.: 

  • Q ≤ 500

서브태스크 2 (64점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

17
queryreuq--------

예제 출력 1

1 2 3 4 5 7 9 11 13 11 9 7 5 4 3 2 1
W3sicHJvYmxlbV9pZCI6IjE1NzcwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUXVlcnlyZXVRIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTBcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI0YTRcdWM5ZDFcdWM1YjRcdWIzYzQgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWIwOThcdWM2MjhcdWIyZTQgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCA8c3Ryb25nPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YzxcL3N0cm9uZz5cdWM3NzRcdWI3N2MgXHViZDgwXHViOTc4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAmcXVvdDthJnF1b3Q7LCAmcXVvdDthYSZxdW90OywgJnF1b3Q7YXBwYSZxdW90OywgJnF1b3Q7cXVlcnlyZXVxJnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViYWE4XHViNDUwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgPGVtPlM8XC9lbT5cdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjYzk4XHViOWFjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT48ZW0+UzxcL2VtPlx1Yzc1OCBcdWI5ZTggXHViNGE0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI5N2MgXHVkNTU4XHViMDk4IFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+PGVtPlM8XC9lbT5cdWM3NTggXHViOWU4IFx1YjRhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1Y2M5OFx1YjlhY1x1ZDU1YyBcdWQ2YzQsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWQ1NzRcdWIyZjkgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCA8c3Ryb25nPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyBcdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjQ8XC9zdHJvbmc+XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgPGVtPlM8XC9lbT5cdWM2NDAgMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPmo8XC9lbT4gJmxlOyB8PGVtPlM8XC9lbT58XHVjNzc4IFx1YzgxNVx1YzIxOCA8ZW0+aTxcL2VtPiwmbmJzcDs8ZW0+ajxcL2VtPlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIDxlbT5TPFwvZW0+WzxlbT5pPFwvZW0+LCA8ZW0+ajxcL2VtPl1cdWI5N2MgPGVtPlM8XC9lbT5cdWM3NTggPGVtPmk8XC9lbT5cdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHViZDgwXHVkMTMwIDxlbT5qPFwvZW0+XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YWU0Y1x1YzljMFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0IFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWM4MTVcdWM3NThcdWQ1NThcdWM3OTAuIFx1YjJmOVx1YzJlMFx1Yzc0MCBTW2ksIGpdXHVhYzAwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHVjMzBkICg8ZW0+aTxcL2VtPiwmbmJzcDs8ZW0+ajxcL2VtPilcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YzViNFx1YzExYywgXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMTggPGVtPlE8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM3YWMgXHVjOTA0XHVjNWQwIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWFlMzhcdWM3NzQgPGVtPlE8XC9lbT5cdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzkxMSA8ZW0+aTxcL2VtPlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAgPGVtPks8c3ViPmk8XC9zdWI+PFwvZW0+XHViMjk0IDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD48ZW0+SzxzdWI+aTxcL3N1Yj48XC9lbT5cdWIyOTQgJiMzOTs8Y29kZT4tPFwvY29kZT4mIzM5OyBcdWM3NzRcdWFjNzBcdWIwOTgsIFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTAgKCYjMzk7PGNvZGU+YTxcL2NvZGU+JiMzOTssICYjMzk7PGNvZGU+YjxcL2NvZGU+JiMzOTssIC4uLiwgJiMzOTs8Y29kZT56PFwvY29kZT4mIzM5OykgXHVjOTExXHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gKFx1YjUzMFx1YzYzNFx1ZDQ1Y1x1YjI5NCBcdWM4MWNcdWM2NzhcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YWMwMCAmIzM5Ozxjb2RlPi08XC9jb2RlPiYjMzk7XHVjNzc0XHViNzdjXHViYTc0LCA8ZW0+UzxcL2VtPlx1Yzc1OCBcdWI5ZTggXHViNGE0XHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM2MDFcdWM1YjQgXHVjMThjXHViYjM4XHVjNzkwXHViNzdjXHViYTc0IDxlbT5TPFwvZW0+XHVjNzU4IFx1YjllOCBcdWI0YTRcdWM1ZDAgPGVtPks8c3ViPmk8XC9zdWI+PFwvZW0+XHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjYzk4XHViOWFjXHVkNTVjIFx1Yzc3NFx1ZDZjNCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVkNTZkXHVjMGMxIDEgXHVjNzc0XHVjMGMxXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC4mbmJzcDsmbmJzcDsgJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjIFx1YzkwNFx1YzVkMCA8ZW0+UTxcL2VtPlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjOTExIDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCA8ZW0+aTxcL2VtPlx1YmM4OFx1YzlmOCBcdWNmZmNcdWI5YWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0IiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyA8ZW0+UTxcL2VtPiAmbGU7IDEwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5cdWM3NzQgXHVjMTFjXHViZTBjXHVkMGRjXHVjMmE0XHVkMDZjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48ZW0+UTxcL2VtPiAmbGU7IDUwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8cD5cdWM3NzQgXHVjMTFjXHViZTBjXHVkMGRjXHVjMmE0XHVkMDZjXHViMjk0IFx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWQ1NWMgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNTc3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZXJ5cmV1USIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJpbmcgaXMgPHN0cm9uZz5wYWxpbmRyb21lPFwvc3Ryb25nPiwgaWYgdGhlIHN0cmluZyByZWFkcyB0aGUgc2FtZSBiYWNrd2FyZCBhbmQgZm9yd2FyZC4gRm9yIGV4YW1wbGUsIHN0cmluZ3MgbGlrZSAmcXVvdDthJnF1b3Q7LCAmcXVvdDthYSZxdW90OywgJnF1b3Q7YXBwYSZxdW90OywgJnF1b3Q7cXVlcnlyZXVxJnF1b3Q7IGFyZSBhbGwgcGFsaW5kcm9tZXMuPFwvcD5cclxuXHJcbjxwPkZvciBnaXZlbiBlbXB0eSBzdHJpbmcgPGVtPlM8XC9lbT4sIHlvdSBzaG91bGQgcHJvY2VzcyBmb2xsb3dpbmcgdHdvIHF1ZXJpZXMgOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkFkZCBhIGxvd2VyIGNhc2UgYWxwaGFiZXQgYXQgdGhlIGJhY2sgb2YgPGVtPlM8XC9lbT4uPFwvbGk+XHJcblx0PGxpPlJlbW92ZSBhIGNoYXJhY3RlciBhdCB0aGUgYmFjayBvZiA8ZW0+UzxcL2VtPi48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5BZnRlciBwcm9jZXNzaW5nIGEgcXVlcnksIHlvdSBzaG91bGQgY291bnQgdGhlIG51bWJlciBvZiA8c3Ryb25nPnBhbGluZHJvbWUgc3Vic3RyaW5nPFwvc3Ryb25nPiZuYnNwO2luIDxlbT5TPFwvZW0+LiBGb3Igc3RyaW5nIDxlbT5TPFwvZW0+Jm5ic3A7YW5kIGludGVnZXJzIDxlbT5pPFwvZW0+LCA8ZW0+ajxcL2VtPiZuYnNwOygxICZsZTsgPGVtPmk8XC9lbT4gJmxlOyA8ZW0+ajxcL2VtPiAmbGU7IHw8ZW0+UzxcL2VtPnwpLCA8ZW0+UzxcL2VtPls8ZW0+aTxcL2VtPiwgPGVtPmo8XC9lbT5dIHJlcHJlc2VudHMgYSBzdWJzdHJpbmcgZnJvbSA8ZW0+aTxcL2VtPnRoIHRvIDxlbT5qPFwvZW0+dGggY2hhcmFjdGVyIG9mIDxlbT5TPFwvZW0+LiBZb3Ugc2hvdWxkIHByaW50IG91dCB0aGUgbnVtYmVyIG9mIGludGVnZXIgcGFpcnMgKDxlbT5pPFwvZW0+LCA8ZW0+ajxcL2VtPikgd2hlcmUgPGVtPlM8XC9lbT5bPGVtPmk8XC9lbT4sIDxlbT5qPFwvZW0+XSBpcyBwYWxpbmRyb21lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgdHdvIGxpbmVzLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZmlyc3QgbGluZSwgPGVtPlE8XC9lbT4sIHRoZSBudW1iZXIgb2YgcXVlcmllcyBpcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHNlY29uZCBsaW5lLCB0aGUgcXVlcnkgaXMgZ2l2ZW4gYXMgc3RyaW5nIG9mIGxlbmd0aCA8ZW0+UTxcL2VtPi4gPGVtPmk8XC9lbT50aCBjaGFyYWN0ZXIgPGVtPks8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7ZGVub3RlcyB0aGUgPGVtPmk8XC9lbT50aCBxdWVyeS48XC9wPlxyXG5cclxuPHA+PGVtPks8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7aXMgJiMzOTs8Y29kZT4tPFwvY29kZT4mIzM5OyBvciBsb3dlciBjYXNlIGFscGhhYmV0ICgmIzM5Ozxjb2RlPmE8XC9jb2RlPiYjMzk7LCAmIzM5Ozxjb2RlPmI8XC9jb2RlPiYjMzk7LCAuLi4sICYjMzk7PGNvZGU+ejxcL2NvZGU+JiMzOTspICh3aXRob3V0IHF1b3RlcykuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBjaGFyYWN0ZXIgaXMgJiMzOTs8Y29kZT4tPFwvY29kZT4mIzM5OywgeW91IHNob3VsZCByZW1vdmUgYSBjaGFyYWN0ZXIgYXQgdGhlIGJhY2sgb2YgPGVtPlM8XC9lbT4uIElmIHRoZSBjaGFyYWN0ZXIgaXMgbG93ZXIgY2FzZSBhbHBoYWJldCwgeW91IHNob3VsZCBhZGQgYSBjaGFyYWN0ZXIgPGVtPks8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7YXQgdGhlIGJhY2sgb2YgPGVtPlM8XC9lbT4uPFwvcD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCBsZW5ndGggb2YgPGVtPlM8XC9lbT4mbmJzcDtpcyBhbHdheXMgcG9zaXRpdmUgYWZ0ZXIgdGhlIHF1ZXJ5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IG91dCA8ZW0+UTxcL2VtPiZuYnNwO3NwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBpbiB0aGUgZmlyc3QgbGluZS4gPGVtPmk8XC9lbT4tdGggaW50ZWdlciBzaG91bGQgYmUgdGhlIGFuc3dlciBvZiB0aGUgPGVtPmk8XC9lbT50aCBxdWVyeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IDxlbT5RPFwvZW0+ICZsZTsgMTAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPlRoaXMgc3VidGFzayBoYXMgYWRkaXRpb25hbCBjb25zdHJhaW50cyA6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPlE8XC9lbT4gJmxlOyA1MDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHA+VGhpcyBzdWJ0YXNrIGhhcyBubyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==

출처

University > KAIST > 2018 KAIST RUN Spring Contest Q번

  • 문제를 만든 사람: koosaga
  • 문제의 오타를 찾은 사람: wookje

채점

  • 예제는 채점하지 않는다.