[Problem link][1]
[My code][2]
I have implemented the Rabin-Karp algorithm and still it’s exceeding the time limit. Any suggestions for making it faster??
[1]: SPOJ.com - Problem NHAY
[2]: Izpg4B - Online C++ Compiler & Debugging Tool - Ideone.com
1 Like
@gautam94:First of all the Rabin-Karp algorithm won’t ever run within the time limit as the worst case complexity of this algorithm is O(nm) where n is the length of the input string and m is the length of the substring.Hence,for larger values of n and m (in the order of 10^5 or more ),this won’t run within the time bound.
Therefore you need to use better algorithm.(I won’t be telling you rather I want you to find it by yourself).
1 Like
I am doing the similar problem but I am able to solve the problem with Rabin-Karp but Rabin-Karp takes hell lot of time.
@gautam94 You are using memset inside while loop because of which in each test case the complexity becomes equal to the maximum size of the arrays.There may be test cases where length of pattern and text is very very less than 10^5 but due to memset your code will still perform operations equal to the maximum size of the arrays.
1 Like
@knb_dtu You have already commented there which algorithm is to be used so I don’t need to guess and there’s a comment on the next page which says it can be solved by Rabin-Karp method. Maybe the test data is weak or the maximum length of the input string is much shorter than 10^5.
robin-karp won’t pass… try something else
@chandan721 But in my implementation I am not checking for collisions so the worst case of my code should be O(n), right?
1 Like