시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 409 108 80 23.055%

문제

알파벳 소문자들로만 이루어진 문자열을 생각하자. 이런 문자열을 읽어 나가다 보면, 문자열의 주기가 예측되는 순간이 있다. 다음과 같은 문자열을 예로 들어 보자.

a b a b a b a

이 문자열을 네 번째 문자까지의 문자열 'a b a b'와, 그 뒤에 남은 'a b a'로 나누어 생각해 볼 수 있다. 이렇게 하면 뒤쪽 문자열은 앞쪽 네 개의 문자 중 세 번째 문자까지가 반복되다가 끝나는 꼴이다.

a b a b a b a

또한, 여섯 번째 문자까지의 문자열 'a b a b a b'와, 그 뒤에 남은 'a'로 나누어서 생각할 수도 있다. 이 경우에도 뒤쪽 문자열은 앞쪽 문자열이 반복되다가 끝나는 꼴이다.

즉, 예시된 문자열은 'a b a b'혹은, 'a b a b a b'가 반복되는 문자열의 일부라고 예상할 수 있는 것이다. 단, 이러한 추정에서 뒤쪽 문자열이 앞쪽 문자열보다 길면 안 된다. 예를 들어 'a b'는 이 문자열의 주기로 예측하기에는 너무 짧다.

이제는 어떤 문자열 S에 대해, 첫 번째 문자부터, i번째 문자까지로 이루어진 부분 문자열 Si를 생각해 보자. 모든  각각에 대해, 위에 예시된 것처럼 문자열의 주기를 추정할 수 있다. 우리가 관심 있는 것은 이렇게  각각에 Si대해 추정할 수 있는 주기 중 가장 긴 것의 길이이다. 이를 Pi라고 하자. 예시된 문자열에서 P7은 4와 6 중 최대값인 6이 된다.

길이가 n인 문자열 S가 주어졌을 때, P1+P2+...+Pn을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S의 길이 n이 주어진다. (1<=n<=1,000,000) 둘째 줄에 문자열 S가 공백 없이 주어진다.

출력

첫째 줄에, P1+P2+...+Pn의 값을 출력한다.

예제 입력 1

8
babababa

예제 출력 1

24

힌트

P8 = 6, P7 = 6, P6 = 4, P5 = 4, P4 = 2, P3 = 2, P2 = 0, P1 = 0

W3sicHJvYmxlbV9pZCI6IjE3ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjOGZjXHVhZTMwIFx1YzYwOFx1Y2UyMSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViN2YwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3N2RcdWM1YjQgXHViMDk4XHVhYzAwXHViMmU0IFx1YmNmNFx1YmE3NCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzhmY1x1YWUzMFx1YWMwMCBcdWM2MDhcdWNlMjFcdWI0MThcdWIyOTQgXHVjMjFjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNjA4XHViODVjIFx1YjRlNFx1YzViNCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPmEgYiBhIGIgYSBiIGE8XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJiMzOTthIGIgYSBiJiMzOTtcdWM2NDAsIFx1YWRmOCBcdWI0YTRcdWM1ZDAgXHViMGE4XHVjNzQwICYjMzk7YSBiIGEmIzM5O1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjMGRkXHVhYzAxXHVkNTc0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViYTc0IFx1YjRhNFx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTVlXHVjYWJkIFx1YjEyNCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwIFx1YzkxMSBcdWMxMzggXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YWU0Y1x1YzljMFx1YWMwMCBcdWJjMThcdWJjZjVcdWI0MThcdWIyZTRcdWFjMDAgXHViMDVkXHViMDk4XHViMjk0IFx1YWYzNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+YSBiIGEgYiBhIGIgYTxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMsIFx1YzVlY1x1YzEyZiBcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCAmIzM5O2EgYiBhIGIgYSBiJiMzOTtcdWM2NDAsIFx1YWRmOCBcdWI0YTRcdWM1ZDAgXHViMGE4XHVjNzQwICYjMzk7YSYjMzk7XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjNjNCBcdWI0YTRcdWNhYmQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU1ZVx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViYzE4XHViY2Y1XHViNDE4XHViMmU0XHVhYzAwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWFmMzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjNjA4XHVjMmRjXHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmIzM5O2EgYiBhIGImIzM5O1x1ZDYzOVx1Yzc0MCwgJiMzOTthIGIgYSBiIGEgYiYjMzk7XHVhYzAwIFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjNzdjXHViZDgwXHViNzdjXHVhY2UwIFx1YzYwOFx1YzBjMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmU4LCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjZDk0XHVjODE1XHVjNWQwXHVjMTFjIFx1YjRhNFx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNTVlXHVjYWJkIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YmNmNFx1YjJlNCBcdWFlMzhcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAmIzM5O2EgYiYjMzk7XHViMjk0IFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjOGZjXHVhZTMwXHViODVjIFx1YzYwOFx1Y2UyMVx1ZDU1OFx1YWUzMFx1YzVkMFx1YjI5NCBcdWIxMDhcdWJiMzQgXHVjOWU3XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWJkODBcdWQxMzAsIGlcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhZTRjXHVjOWMwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFNpXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1YmFhOFx1YjRlMCZuYnNwOyBcdWFjMDFcdWFjMDFcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM3MDRcdWM1ZDAgXHVjNjA4XHVjMmRjXHViNDFjIFx1YWM4M1x1Y2M5OFx1YjdmYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjOGZjXHVhZTMwXHViOTdjIFx1Y2Q5NFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWFjMDAgXHVhZDAwXHVjMmVjIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNzc0XHViODA3XHVhYzhjJm5ic3A7IFx1YWMwMVx1YWMwMVx1YzVkMCBTaVx1YjMwMFx1ZDU3NCBcdWNkOTRcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4ZmNcdWFlMzAgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhYzgzXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViOTdjIFBpXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNjA4XHVjMmRjXHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBQN1x1Yzc0MCA0XHVjNjQwIDYgXHVjOTExIFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc3OCA2XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgUDErUDIrLi4uK1BuXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yzc1OCBcdWFlMzhcdWM3NzQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmx0Oz1uJmx0Oz0xLDAwMCwwMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVhY2Y1XHViYzMxIFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgUDErUDIrLi4uK1BuXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlA4ID0gNiwgUDcgPSA2LCBQNiA9IDQsIFA1ID0gNCwgUDQgPSAyLCBQMyA9IDIsIFAyID0gMCwgUDEgPSAwPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVyaW9kcyBvZiBXb3JkcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJpbmcgaXMgYSBmaW5pdGUgc2VxdWVuY2Ugb2YgbG93ZXItY2FzZSAobm9uLWNhcGl0YWwpIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFBhcnRpY3VsYXJseSwgaXQgbWF5IGJlIGFuIGVtcHR5IHNlcXVlbmNlLCBpLmUuIGEgc2VxdWVuY2Ugb2YgMCBsZXR0ZXJzLiBCeSBBID0gQkMgd2UgZGVub3RlcyB0aGF0IEEgaXMgYSBzdHJpbmcgb2J0YWluZWQgYnkgY29uY2F0ZW5hdGlvbiAoam9pbmluZyBieSB3cml0aW5nIG9uZSBpbW1lZGlhdGVseSBhZnRlciBhbm90aGVyLCBpLmUuIHdpdGhvdXQgYW55IHNwYWNlLCBldGMuKSBvZiB0aGUgc3RyaW5ncyBCIGFuZCBDIChpbiB0aGlzIG9yZGVyKS4gQSBzdHJpbmcgUCBpcyBhIHByZWZpeCBvZiB0aGUgc3RyaW5nIEEsIGlmIHRoZXJlIGlzIGEgc3RyaW5nIEIsIHRoYXQgQSA9IFBCLiBJbiBvdGhlciB3b3JkcywgcHJlZml4ZXMgb2YgQSBhcmUgdGhlIGluaXRpYWwgZnJhZ21lbnRzIG9mIEEuIEluIGFkZGl0aW9uLCBpZiBQICZuZTsgQSBhbmQgUCBpcyBub3QgYW4gZW1wdHkgc3RyaW5nLCB3ZSBzYXksIHRoYXQgUCBpcyBhIHByb3BlciBwcmVmaXggb2YgQS48XC9wPlxyXG5cclxuPHA+QSBzdHJpbmcgUSBpcyBhIHBlcmlvZCBvZiBBLCBJZiBRIGlzIHByb3BlciBwcmVmaXggb2YgQSBhbmQgQSBpcyBhIHByZWZpeCAobm90IG5lY2Vzc2FyaWx5IGEgcHJvcGVyIG9uZSkgb2YgdGhlIHN0cmluZyBRUS4gRm9yIGV4YW1wbGUsIHRoZSBzdHJpbmdzIDxjb2RlPmFiYWI8XC9jb2RlPiBhbmQgPGNvZGU+YWJhYmFiPFwvY29kZT4gYXJlIGJvdGggcGVyaW9kcyBvZiB0aGUgc3RyaW5nIDxjb2RlPmFiYWJhYmE8XC9jb2RlPi4gVGhlIG1heGltdW0gcGVyaW9kIG9mIGEgc3RyaW5nIEEgaXMgdGhlIGxvbmdlc3Qgb2YgaXRzIHBlcmlvZHMgb3IgdGhlIGVtcHR5IHN0cmluZywgSWYgYSBkb2VzbiYjMzk7dCBoYXZlIGFueSBwZXJpb2QuIEZvciBleGFtcGxlLCB0aGUgbWF4aW11bSBwZXJpb2Qgb2YgPGNvZGU+YWJhYmFiPFwvY29kZT4gaXMgPGNvZGU+YWJhYjxcL2NvZGU+LiBUaGUgbWF4aW11bSBwZXJpb2Qgb2YgPGNvZGU+YWJjPFwvY29kZT4gaXMgdGhlIGVtcHR5IHN0cmluZy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgc3RyaW5nJiMzOTtzIGxlbmd0aCBhbmQgdGhlIHN0cmluZyBpdHNlbGYsPFwvbGk+XHJcblx0PGxpPmNhbGN1bGF0ZXMgdGhlIHN1bSBvZiBsZW5ndGhzIG9mIG1heGltdW0gcGVyaW9kcyBvZiBhbGwgaXRzIHByZWZpeGVzLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlcmUgaXMgb25lIGludGVnZXIgayAoMSAmbGU7IGsgJmxlOyAxIDAwMCAwMDApIC0gdGhlIGxlbmd0aCBvZiB0aGUgc3RyaW5nLiBJbiB0aGUgZm9sbG93aW5nIGxpbmUgYSBzZXF1ZW5jZSBvZiBleGFjdGx5IGsgbG93ZXItY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0IGlzIHdyaXR0ZW4gLSB0aGUgc3RyaW5nLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHlvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSBhbiBpbnRlZ2VyIC0gdGhlIHN1bSBvZiBsZW5ndGhzIG9mIG1heGltdW0gcGVyaW9kcyBvZiBhbGwgcHJlZml4ZXMgb2YgdGhlIHN0cmluZyBnaXZlbiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==