[closed] COOK103B - SECPASS TLE problem

general
,
1

Hi,

I tried to implement the KMP search algorithm (gfg) for this question SECPASS. I thought the complexity of it is O(M+N). Can someone please tell me the O complexity required to solve this question and the problem in my code?

My code

Cheers Aadarsh…

2

I did the same thing at first and used the KMP O(M+N) Algorithm in C++ (Copied from GeeksForGeeks). But then I was getting a TLE of 0.01 seconds so I switched to the KMP O(M*N) Alg (Also from GeeksForGeeks) and got AC.

3

Could you give me a link to the algorithm @satyankar_2005 ? I’m having a hard time finding it.

4

You are calling the KMP algorithm for N times (for each possible prefix). So, the complexity becomes O(N*(M+N)).
Hint: Computing the lps array and applying some operations on it is enough to solve this problem (I didn’t solve it but I guess that will be enough)

1 Like
5

I tried implementing @l_returns code in Python: https://www.codechef.com/viewsolution/23131022

I think his code and mine match exactly.

My code: https://www.codechef.com/viewsolution/23143654

Could you please help me @utkarsh911 ?

6

Not your fault.
For some questions, you have to switch to a faster language. Python isn’t fast enough to pass the time limit even after the adjustments with the multiplier.
Clearly, both the code are using the same algorithm, one gets AC another is getting TLE.
I don’t know anything about python but unless there is something like infinite loop or something in your code, it’s not your fault that you got TLE.

1 Like
7

It’s TLE because of strict time limit and slow python…

8

Because intended solution was O(|s|) instead

1 Like
9

Thank you, guys. Since, Python is slower in implementing the KMP algorithm, I decided to use a different approach for attacking the problem, in order to reduce the time complexity to O(|s|). Appreciate the help @l_returns @utkarsh911 !

My approach: https://www.codechef.com/viewsolution/23144643

10

XD nice solution… I love python for the same thing…