10298 - Power Strings

[brianfry713]

There are a few ways to solve this problem.
One that gets AC in 0.085 seconds is to check if the string is k copies of a len / k substring, where k is prime. Test all primes up to sqrt(len). If you can then recursively return k * the result of checking the len / k substring. If not then return 1.

Learning algorithms through google translate is not ideal.
http://en.wikipedia.org/wiki/Knuth%E2%8 ... _algorithm

[Nur13]

WHY TLE?????

Code: Select all

#include<bits/stdc++.h>
using namespace std;

string strret(string A,int i,int j)
{
    string res;
    int g;
    for(g=i;g<=j;g++)
    {
        res+=A[g];
    }
    return res;
}

int main()
{
    string A;
    int i,j,k;
    while(cin>>A)
    {
        int cnt=1;
        string B=strret(A,0,0);
        int Size=A.size();
        int x=1,y=1,prev;
        int g=1;
        int bsize=1;
        while(bsize<=Size/2 && y<Size)
        {
            //cout<<Size<<endl;
            //cout<<x<<" "<<y<<endl;
            string C=strret(A,x,y);
            //cout<<B<<" "<<C<<endl;
            prev=y;
            if(B==C){cnt++;x+=bsize+1;y+=bsize+1;}
            else{
              //  cout<<"c";
                cnt=1;
                B=strret(A,0,g);
                bsize=g;
                x=g+1;
                y=2*(g)+1;
                g++;
            }
        }
        if(prev!=Size-1)cnt=1;
        cout<<cnt<<endl;

    }

}