10298 - Power Strings

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10298 - Power Strings

Post by brianfry713 » Wed Jan 21, 2015 11:48 pm

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
Check input and AC output for thousands of problems on uDebug!

Nur13
New poster
Posts: 1
Joined: Fri May 20, 2016 6:19 am

Re: 10298 - Power Strings

Post by Nur13 » Fri May 20, 2016 6:23 am

WHY TLE????? :o


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;

    }

}




Post Reply

Return to “Volume 102 (10200-10299)”