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

#include<string.h>

#include<stdio.h>

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

``````int t;

scanf("%d",&t);
while(t>0)
``````

{
int flag=0;

``````scanf("%s",&a);
scanf("%s",&b);
for(int i=0;i<strlen(a);i++)
{
for(int j=0;j<strlen(b);j++)
{
if(a[i]==b[j]){
flag++;
b[j]='1';
break;
}
}
}
printf("%d",flag);

t--;
``````

}

}

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.

2 Likes

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.
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.

//