ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1423. String Tale

TLE on #8
Posted by Shervin 11 Feb 2015 09:24
I'm using KMP I don't know why I get TLE?

#include <iostream>

int main(int argc, const char * argv[]) {

long long int NumofChars;
long long int finAns=-1;

scanf("%lld",&NumofChars);

char lettersT[NumofChars];
char letter_tmp;

for (long long int i=0;i<NumofChars;i++)
{
scanf(" %c",&letter_tmp);
lettersT[i]=letter_tmp;
}

for (long long int i=0;i<NumofChars;i++)
{
scanf(" %c",&letter_tmp);
}

long long int prefix[NumofChars];
prefix[0]=0;
prefix[1]=0;

long long int pi=0;
long long int pj=1;

while(pj<NumofChars-1)
{
if(lettersT[pi]==lettersT[pj])
{
prefix[pj+1]=prefix[pj]+1;

pi++;
pj++;

}
else
{

pi=0;
if(lettersT[pi]==lettersT[pj])
{
prefix[pj+1]=1;

pi++;
pj++;

}
else
{
prefix[pj+1]=0;

pj++;

}

}
}

finAns=-1;

long long int i=0;
while(i<NumofChars)
{

long long int Matchcount=0;
long long int j_init=0;
for (long long int j=j_init;j<NumofChars;j++)
{
{
Matchcount++;
}
else
{
if(j-prefix[j]>0)
{
i=i+j-prefix[j];
j_init=prefix[j];

}
else
{
i++;
}

break;
}
}

if(Matchcount==NumofChars)
{
finAns=i;

break;
}
}
std::cout<<finAns;
return 0;
}