시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1720 458 344 36.596%

문제

알파벳 소문자로 이루어진 두 문자열 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
W3sicHJvYmxlbV9pZCI6IjQzNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjODFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBhKmJcdWIyOTQgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM1YjRcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgYT0mcXVvdDthYmMmcXVvdDssIGI9JnF1b3Q7ZGVmJnF1b3Q7XHVjNzdjIFx1YjU0YywgYSpiPSZxdW90O2FiY2RlZiZxdW90O1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWNmMVx1YzE0OFx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzU4IFx1YzgxY1x1YWNmMVx1YjNjNCBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hXjAgPSAmcXVvdDsmcXVvdDsgKFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQpPFwvbGk+XHJcblx0PGxpPmFeKG4rMSkgPSBhKihhXm4pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0IHNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBhXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBzPWFeblx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBuXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBzXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1YyBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIHNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCAxXHVjNzc0XHViYTcwLCBcdWJjMzFcdWI5Y2NcdWFlMDBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViMmU0XHVjNzRjIFx1YzkwNFx1Yzc0MCBcdWI5YzhcdWNlNjhcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBzPWFeblx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBuXHVjNzQ0IFx1Y2MzZVx1Yzc0MCBcdWI0YTQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzNTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb3dlciBTdHJpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiB0d28gc3RyaW5ncyBhIGFuZCBiIHdlIGRlZmluZSBhKmIgdG8gYmUgdGhlaXIgY29uY2F0ZW5hdGlvbi4gRm9yIGV4YW1wbGUsIGlmIGEgPSAmcXVvdDthYmMmcXVvdDsgYW5kIGIgPSAmcXVvdDtkZWYmcXVvdDsgdGhlbiBhKmIgPSAmcXVvdDthYmNkZWYmcXVvdDsuIElmIHdlIHRoaW5rIG9mIGNvbmNhdGVuYXRpb24gYXMgbXVsdGlwbGljYXRpb24sIGV4cG9uZW50aWF0aW9uIGJ5IGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgaXMgZGVmaW5lZCBpbiB0aGUgbm9ybWFsIHdheTogYV4wID0gJnF1b3Q7JnF1b3Q7ICh0aGUgZW1wdHkgc3RyaW5nKSBhbmQgYV4obisxKSA9IGEqKGFebikuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBpcyBhIGxpbmUgb2YgaW5wdXQgcmVwcmVzZW50aW5nIHMsIGEgc3RyaW5nIG9mIGxvd2VyLWNhc2UgYWxwaGFiZXRpYyBjaGFyYWN0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHMgeW91IHNob3VsZCBwcmludCB0aGUgbGFyZ2VzdCBuIHN1Y2ggdGhhdCBzID0gYV5uIGZvciBzb21lIHN0cmluZyBhLiBUaGUgbGVuZ3RoIG9mIHMgd2lsbCBiZSBhdCBsZWFzdCAxIGFuZCB3aWxsIG5vdCBleGNlZWQgMSBtaWxsaW9uIGNoYXJhY3RlcnMuIEEgbGluZSB3aXRoIGEgcGVyaW9kIGZvbGxvd3MgdGhlIGxhc3QgdGVzdCBjYXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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