2406:Power Strings

keyword

約数　文字列　C++

概要

文字列s(strlen(s) < 1000000)が与えられる。s=a^nなる最大のnを求める問題。
候補はstrlen(s)の約数だけ。またs=a^nであるかどうかの判定はO(strlen(s))でできる。
約数の個数が多いと怪しいけどとりあえず投げてみたら通った。

int main(){
    char str[1000001];
    int n, i, j, k, s, ans;
    while(scanf("%s\n",str)){
        if(!strcmp(str,".")) break;
        n = strlen(str);
        ans = 1;
        vector<int> fs;

        for(i=n;i>=2;i--){
            if(!(n%i)) fs.PB(i);
        }
        s = SZ(fs);

        REP(i,s){
            int step = n/fs[i];
            for(j=0;j<step;j++){
                for(k=j+step;k<n;k+=step)if(str[k-step]!=str[k])break;
                if(k<n)break;
            }
            if(j==step)break;
        }
        if(i<s) ans = fs[i];

        printf("%d\n",ans);
    }

    return 0;
}