PKU 2406 Power Strings

http://poj.org/problem?id=2406
文字列aとbがある時、a*bはaの後ろにbをつなげたものを意味する。(stringクラスでいうところのa+b)。また、a^n=a*(a^(n-1))となるとする。
この時、文字列sが与えられ、a^n=sとなるような最大のnを求めるという問題。

やや易？

TLEが怖かったが、愚直にやっても多少余裕はあった。100ms台でACするアルゴリズムがきになる。

char in[1000010];

main(){
  while(scanf("%s",in)){
    if(in[0]=='.')break;
    int len=strlen(in);
    int ans=0;
    for(int i=1;i<=len;i++){
      if(len%i)continue;
      int pos=0;
      while(i+pos<len && in[pos%i]==in[pos+i])++pos;
      if(i+pos==len){
	ans=len/i;
	break;
      }
    }
    printf("%d\n",ans);
  }
}