## 10298 - Power Strings

Moderator: Board moderators

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

### Re: 10298 - Power Strings

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

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;

}

}

``````