my code for longest common pattern(Problem code: LCPESY) is showing TLE..plz plz any one help 4 dat..........



int main()
char a[10000],b[10000];

int t;


int flag=0;

for(int i=0;i<strlen(a);i++)
	for(int j=0;j<strlen(b);j++)




First of all, always remember that strlen() function is an O(n) function to calculate the length of a string. So, doing “for(i=0;i< strlen(a);i++)” makes the loop O(n^2) instead of O(n). Your two for loops were therefore performing O(n^4) to calculate the answer.
Now t is 100 and n is 1000 so that makes your solution O(tn^4) which is not possible to run in 1 sec.
Even making an O(t
n^2) solution would give a TLE as it will be 10^10 which cannot be run in 1 sec.
The correct approach to the question is hashing. Have a look at this. It is the accepted version of your code.


Use Hashing bro. Basically using array indexes for fast access.

1 Like

how cn u calculate the program for in 1 sec or not,is just ur experience in the codechef or there is any sort of calculation regarding this,i undrstnd ur complexity bt cn u explain how does u calculate it for running in 1 sec or not

Its definitely experience. :slight_smile:
Most of the time it will work if your algorithm is not naive. The most basic approach is rarely the solution. (I am sorry i commented for roman28)

Request you to continue the discussion on the editorial page of the problem. Closing this question as of now.