시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1258 301 235 37.480%

문제

두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

a^0 = "" (빈 문자열)

a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표를 포함하고 있다.

출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

예제 입력 1

abcd
aaaa
ababab
.

예제 출력 1

1
4
3
W3sicHJvYmxlbV9pZCI6IjQzNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjODFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBhKmJcdWIyOTQgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM1YjRcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgYT0mcXVvdDthYmMmcXVvdDssIGI9JnF1b3Q7ZGVmJnF1b3Q7XHVjNzdjIFx1YjU0YywgYSpiPSZxdW90O2FiY2RlZiZxdW90O1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWNmMVx1YzE0OFx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzU4IFx1YzgxY1x1YWNmMVx1YjNjNCBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+YV4wID0gJnF1b3Q7JnF1b3Q7IChcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0KTxcL3A+XHJcblxyXG48cD5hXihuKzEpID0gYSooYV5uKTxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgc1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0IGFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIHM9YV5uXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIG5cdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IHNcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gc1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IDFcdWM3NzRcdWJhNzAsIFx1YmMzMVx1YjljY1x1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNzQwIFx1YjljOFx1Y2U2OFx1ZDQ1Y1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgcz1hXm5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgblx1Yzc0NCBcdWNjM2VcdWM3NDAgXHViNGE0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG93ZXIgU3RyaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gdHdvIHN0cmluZ3MgYSBhbmQgYiB3ZSBkZWZpbmUgYSpiIHRvIGJlIHRoZWlyIGNvbmNhdGVuYXRpb24uIEZvciBleGFtcGxlLCBpZiBhID0gJnF1b3Q7YWJjJnF1b3Q7IGFuZCBiID0gJnF1b3Q7ZGVmJnF1b3Q7IHRoZW4gYSpiID0gJnF1b3Q7YWJjZGVmJnF1b3Q7LiBJZiB3ZSB0aGluayBvZiBjb25jYXRlbmF0aW9uIGFzIG11bHRpcGxpY2F0aW9uLCBleHBvbmVudGlhdGlvbiBieSBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIGlzIGRlZmluZWQgaW4gdGhlIG5vcm1hbCB3YXk6IGFeMCA9ICZxdW90OyZxdW90OyAodGhlIGVtcHR5IHN0cmluZykgYW5kIGFeKG4rMSkgPSBhKihhXm4pLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2UgaXMgYSBsaW5lIG9mIGlucHV0IHJlcHJlc2VudGluZyBzLCBhIHN0cmluZyBvZiBwcmludGFibGUgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzIHlvdSBzaG91bGQgcHJpbnQgdGhlIGxhcmdlc3QgbiBzdWNoIHRoYXQgcyA9IGFebiBmb3Igc29tZSBzdHJpbmcgYS4gVGhlIGxlbmd0aCBvZiBzIHdpbGwgYmUgYXQgbGVhc3QgMSBhbmQgd2lsbCBub3QgZXhjZWVkIDEgbWlsbGlvbiBjaGFyYWN0ZXJzLiBBIGxpbmUgY29udGFpbmluZyBhIHBlcmlvZCBmb2xsb3dzIHRoZSBsYXN0IHRlc3QgY2FzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Waterloo's local Programming Contests > 1 June, 2002 D번