시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB127239627929.215%

문제

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

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+XHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViN2YwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3N2RcdWM1YjQgXHViMDk4XHVhYzAwXHViMmU0IFx1YmNmNFx1YmE3NCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzhmY1x1YWUzMFx1YWMwMCBcdWM2MDhcdWNlMjFcdWI0MThcdWIyOTQgXHVjMjFjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNjA4XHViODVjIFx1YjRlNFx1YzViNCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmEgYiBhIGIgYSBiIGE8XC9wcmU+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjEyNCBcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCAmIzM5Ozxjb2RlPmEgYiBhIGI8XC9jb2RlPiYjMzk7XHVjNjQwLCBcdWFkZjggXHViNGE0XHVjNWQwIFx1YjBhOFx1Yzc0MCAmIzM5Ozxjb2RlPmEgYiBhPFwvY29kZT4mIzM5O1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjMGRkXHVhYzAxXHVkNTc0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViYTc0IFx1YjRhNFx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTVlXHVjYWJkIFx1YjEyNCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwIFx1YzkxMSBcdWMxMzggXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YWU0Y1x1YzljMFx1YWMwMCBcdWJjMThcdWJjZjVcdWI0MThcdWIyZTRcdWFjMDAgXHViMDVkXHViMDk4XHViMjk0IFx1YWYzNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuYSBiIGEgYiBhIGIgYTxcL3ByZT5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVjNWVjXHVjMTJmIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWFlNGNcdWM5YzBcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0ICYjMzk7PGNvZGU+YSBiIGEgYiBhIGI8XC9jb2RlPiYjMzk7XHVjNjQwLCBcdWFkZjggXHViNGE0XHVjNWQwIFx1YjBhOFx1Yzc0MCAmIzM5Ozxjb2RlPmE8XC9jb2RlPiYjMzk7XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjNjNCBcdWI0YTRcdWNhYmQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU1ZVx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViYzE4XHViY2Y1XHViNDE4XHViMmU0XHVhYzAwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWFmMzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjNjA4XHVjMmRjXHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmIzM5Ozxjb2RlPmEgYiBhIGI8XC9jb2RlPiYjMzk7XHVkNjM5XHVjNzQwLCAmIzM5Ozxjb2RlPmEgYiBhIGIgYSBiPFwvY29kZT4mIzM5O1x1YWMwMCBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjc3Y1x1YWNlMCBcdWM2MDhcdWMwYzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOCwgXHVjNzc0XHViN2VjXHVkNTVjIFx1Y2Q5NFx1YzgxNVx1YzVkMFx1YzExYyBcdWI0YTRcdWNhYmQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU1ZVx1Y2FiZCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWJjZjRcdWIyZTQgXHVhZTM4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgJiMzOTs8Y29kZT5hIGI8XC9jb2RlPiYjMzk7XHViMjk0IFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjOGZjXHVhZTMwXHViODVjIFx1YzYwOFx1Y2UyMVx1ZDU1OFx1YWUzMFx1YzVkMFx1YjI5NCBcdWIxMDhcdWJiMzQgXHVjOWU3XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWJkODBcdWQxMzAsIGlcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhZTRjXHVjOWMwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFM8c3ViPmk8XC9zdWI+XHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1YmFhOFx1YjRlMCZuYnNwOyBcdWFjMDFcdWFjMDFcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM3MDRcdWM1ZDAgXHVjNjA4XHVjMmRjXHViNDFjIFx1YWM4M1x1Y2M5OFx1YjdmYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjOGZjXHVhZTMwXHViOTdjIFx1Y2Q5NFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWFjMDAgXHVhZDAwXHVjMmVjIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNzc0XHViODA3XHVhYzhjJm5ic3A7IFx1YWMwMVx1YWMwMVx1YzVkMCBTPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDk0XHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOGZjXHVhZTMwIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWM4M1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBQPHN1Yj5pPFwvc3ViPlx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YzYwOFx1YzJkY1x1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgUDxzdWI+NzxcL3N1Yj5cdWM3NDAgNFx1YzY0MCA2XHVjOTExIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3OCA2XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgUDxzdWI+MTxcL3N1Yj4gKyBQPHN1Yj4yPFwvc3ViPiArIC4uLiArIFA8c3ViPm48XC9zdWI+XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yzc1OCBcdWFlMzhcdWM3NzQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBQPHN1Yj4xPFwvc3ViPiArIFA8c3ViPjI8XC9zdWI+ICsgLi4uICsgUDxzdWI+bjxcL3N1Yj5cdWM3NTggXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+UDxzdWI+ODxcL3N1Yj4gPSA2LCBQPHN1Yj43PFwvc3ViPiA9IDYsIFA8c3ViPjY8XC9zdWI+ID0gNCwgUDxzdWI+NTxcL3N1Yj4gPSA0LCBQPHN1Yj40PFwvc3ViPiA9IDIsIFA8c3ViPjM8XC9zdWI+ID0gMiwgUDxzdWI+MjxcL3N1Yj4gPSAwLCBQPHN1Yj4xPFwvc3ViPiA9IDA8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3ODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJpb2RzIG9mIFdvcmRzIiwiZGVzY3JpcHRpb24iOiI8cD5BIHN0cmluZyBpcyBhIGZpbml0ZSBzZXF1ZW5jZSBvZiBsb3dlci1jYXNlIChub24tY2FwaXRhbCkgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gUGFydGljdWxhcmx5LCBpdCBtYXkgYmUgYW4gZW1wdHkgc2VxdWVuY2UsIGkuZS4gYSBzZXF1ZW5jZSBvZiAwIGxldHRlcnMuIEJ5IEEgPSBCQyB3ZSBkZW5vdGVzIHRoYXQgQSBpcyBhIHN0cmluZyBvYnRhaW5lZCBieSBjb25jYXRlbmF0aW9uIChqb2luaW5nIGJ5IHdyaXRpbmcgb25lIGltbWVkaWF0ZWx5IGFmdGVyIGFub3RoZXIsIGkuZS4gd2l0aG91dCBhbnkgc3BhY2UsIGV0Yy4pIG9mIHRoZSBzdHJpbmdzIEIgYW5kIEMgKGluIHRoaXMgb3JkZXIpLiBBIHN0cmluZyBQIGlzIGEgcHJlZml4IG9mIHRoZSBzdHJpbmcgQSwgaWYgdGhlcmUgaXMgYSBzdHJpbmcgQiwgdGhhdCBBID0gUEIuIEluIG90aGVyIHdvcmRzLCBwcmVmaXhlcyBvZiBBIGFyZSB0aGUgaW5pdGlhbCBmcmFnbWVudHMgb2YgQS4gSW4gYWRkaXRpb24sIGlmIFAgJm5lOyBBIGFuZCBQIGlzIG5vdCBhbiBlbXB0eSBzdHJpbmcsIHdlIHNheSwgdGhhdCBQIGlzIGEgcHJvcGVyIHByZWZpeCBvZiBBLjxcL3A+XHJcblxyXG48cD5BIHN0cmluZyBRIGlzIGEgcGVyaW9kIG9mIEEsIElmIFEgaXMgcHJvcGVyIHByZWZpeCBvZiBBIGFuZCBBIGlzIGEgcHJlZml4IChub3QgbmVjZXNzYXJpbHkgYSBwcm9wZXIgb25lKSBvZiB0aGUgc3RyaW5nIFFRLiBGb3IgZXhhbXBsZSwgdGhlIHN0cmluZ3MgPGNvZGU+YWJhYjxcL2NvZGU+IGFuZCA8Y29kZT5hYmFiYWI8XC9jb2RlPiBhcmUgYm90aCBwZXJpb2RzIG9mIHRoZSBzdHJpbmcgPGNvZGU+YWJhYmFiYTxcL2NvZGU+LiBUaGUgbWF4aW11bSBwZXJpb2Qgb2YgYSBzdHJpbmcgQSBpcyB0aGUgbG9uZ2VzdCBvZiBpdHMgcGVyaW9kcyBvciB0aGUgZW1wdHkgc3RyaW5nLCBJZiBBIGRvZXNuJiMzOTt0IGhhdmUgYW55IHBlcmlvZC4gRm9yIGV4YW1wbGUsIHRoZSBtYXhpbXVtIHBlcmlvZCBvZiA8Y29kZT5hYmFiYWI8XC9jb2RlPiBpcyA8Y29kZT5hYmFiPFwvY29kZT4uIFRoZSBtYXhpbXVtIHBlcmlvZCBvZiA8Y29kZT5hYmM8XC9jb2RlPiBpcyB0aGUgZW1wdHkgc3RyaW5nLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBzdHJpbmcmIzM5O3MgbGVuZ3RoIGFuZCB0aGUgc3RyaW5nIGl0c2VsZiw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyB0aGUgc3VtIG9mIGxlbmd0aHMgb2YgbWF4aW11bSBwZXJpb2RzIG9mIGFsbCBpdHMgcHJlZml4ZXMsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBrICgxICZsZTsgayAmbGU7IDEgMDAwIDAwMCkgLSB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcuIEluIHRoZSBmb2xsb3dpbmcgbGluZSBhIHNlcXVlbmNlIG9mIGV4YWN0bHkgayBsb3dlci1jYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQgaXMgd3JpdHRlbiAtIHRoZSBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgeW91ciBwcm9ncmFtbWUgc2hvdWxkIHdyaXRlIGFuIGludGVnZXIgLSB0aGUgc3VtIG9mIGxlbmd0aHMgb2YgbWF4aW11bSBwZXJpb2RzIG9mIGFsbCBwcmVmaXhlcyBvZiB0aGUgc3RyaW5nIGdpdmVuIGluIHRoZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2005/2006 > Stage 1 2번