時間制限:3000ミリ秒
メモリ制限:65536KB
問題
2つの文字列a,bが与えられたとき、a*bは、文字列a,bを連結したものと定義される。例えば、a="abc", b="def"であるとき、a*b="abcdef"である。すると、文字列の非負整数による累乗は、「a^0="" (空文字列), a^(n+1)=a*(a^n)」と定義される。文字列sが与えられたとき、s=a^nなるaが存在する最大のnを求めるプログラムを作成せよ。
入力
入力は複数のテストケースを含む。各テストケースは、出力可能な文字から構成される文字列sを含む1行からなる。sの長さは、1以上100万以下である。入力の最後の行は、「.」(ピリオド)のみを含む。
出力
それぞれのテストケースに対して、s=a^nなるaが存在する最大のnを含む1行を出力せよ。
入力の例
abcd aaaa ababab .
出力の例
1 4 3
出典
Waterloo local 2002.07.01