Constraints:
1 <= T <= 100
1 <= M <= N <= 30000 (M and N size of 2 string)
Solution:
int main(){
fastIO;
ll t;
string s,a;
cin>>t;
ll xx = t;
while(t--){
cin>>s>>a;
ll ans = 0;
ll ss = s.size();
ll aa = a.size();
FOR(i,0,ss-aa+1){
FOR(j,0,aa){
if(a[j] == s[i+j]) ans++;
}
}
cout<<"Case "<<xx-t<<": "<<ans<<endl;
}
}
What is the time complexity of my code ? I got TLE on 5s. Can anyone please explain ?
It’s O(M*N) , that’s why the TLE
also your solution is not well formatted, and you’re using macros which i have no clue what they are
2 Likes
Sorry for the inconveniences.ll stands for long long. So here m*n is equal to (9 * 10e8). Generally , I know that In 1s approximately 10e5 to 10e7 solution got accepted. Can you clearify it a bit more ?
This is the standard for most OJs
10^8 = 1 sec
So for 9* 10^8 which is approximately 10^9, you’ll take like 10 secs. Which would give TLE
3 Likes