@rishup_nitdgp can you please explain in which scenario this statement will execute ??
Hello, this is very good. I used a n^2 brute force method and got runtime error. I am not very familiar with rolling-hashes and want to learn. Would it be possible if you commented your Hashing class in the answer key? That would be extremely helpful, Thank you so much.
1 Like
Naive string matching with brute force will exceed the time limit right?anyone?
Can anyone tell me what’s wrong in my code? I am getting Wrong Answer Verdict everytime.
LINK:
https://www.codechef.com/viewsolution/33307144
Why do we require to compute lsp1[0] and lsp1[1],can u please elaborate litttle
don’t over-analyse the problem sometimes
The test cases were very poorly designed. Many O(n^2) solutions got accepted.
Looking at the constraints I straight away rejected this brute force solution and was therefore thinking about any other better solution during the entire contest and was unable to solve this problem during the contest.
4 Likes
Designing a solution by keeping the constraints in mind is always recommended. Why waste time on writing a code which will eventually fail due to memory limit or time limit?
The problem here was with the test cases which were not in accordance with the constraints. Many programmers would have discarded this brute force solution by simply looking at the constraints.
6 Likes
Editorial Video Of Chef Chefina and their Friendship using Rabin Karp Algorithm and Prefix Sum is Here!
Check :- Chef Chefina and Their Friendship (CHEFSHIP) | May CookOff Codechef | Rabin Karp n Prefix Sum - YouTube
Subscribe for Latest Editorial Videos!
Enjoy Watching! 
1 Like
i am not able to get where i am getting my code wrong .
Please provide any test case where it get failed.
link to my code: https://www.codechef.com/viewsolution/33313538
Consider this case,
“aaaa”
lps for this string is 3 because “aaa” is a proper suffix which is also a proper prefix. For this problem we can use a simple hack that whenever the length of 2*lps increases length of string(i+1) we will limit that to (i+1)/2 or length of lps of previous valid lps(thats is maximum (i+1)/2).
1 Like
Rabin Karp Algo Solution.
2 Likes
This line is from your code from lpsArray2 function
My hashing class is implemented in a similar way as described here, however, there are a few differences. I’ll try to explain it part by part.
Whenever a new object of it is created, it takes in a string, a prime, and a modulo, and it calls the initialise function.
The initialise function creates the powers array, which stores every power of P modulo MOD. It also creates the rolling hash array.
The way that rolling hash array is created, is:
- hash[i]=(str[i]-'a'+1)+(P*hash[i+1]).
(str[i]-'a'+1) basically assigns a number 1 to 26 to each character a to z.
hash[i] stores the hash of the suffix i to N, instead of the prefix, as in standard implementations. It uses suffix sums. This enables us to get the hash of any range in constant time, as follows:
- Hash of the substring l to r= hash[l]-(hash[r+1]*pow[r-l+1]).
Remember that hash stores the suffix sums. To get hash of the substring l to r, we do hash[l]-hash[r+1]. hash[l] stores the hash of the suffix l to N, while hash[r+1] stores the hash of the suffix r+1 to N. So, we subtract it from hash[l] to get the hash of the substring.
However, we can’t just subtract it directly. Hash of r+1 to N is raised to a certain power in hash[l]. Thus, to remove it, we raise hash[r+1] to the same power, and then subtract it. Try this with a pen and paper, I think you’ll get it. This enables us to get the hash of any substring in constant time.
My implementation can be improved. It computes the power array every time the object is created. However, since we are using the same prime and modulus, we can just create that array once, separately. Even though this doesn’t change the complexity, it saves space and time. Since the time limits weren’t tight, I didn’t change it.
8 Likes
You are assuming if 2* lps[i] == (i+1) then it’s satisfying the requirement
But,
if S = “aaaa” then lps[3] = 3 and length(3+1)==4
The prefix=suffix=“aaa”, in this case the above condition is not satisfied but what I think is that it must satisfy as “aa” can be the prefix and suffix instead of “aaa” .
Please let me know my error in the approach of overlapping prefix and suffix
@rishup_nitgdp
Thank you so much for sharing ! (great explanation)
1 Like
Can someone please tell why my Solution is giving wrong answer. I have used the same approach as used in setter’s solution.
https://www.codechef.com/viewsolution/33323587
Any help would be appreciated
You are doing a lot of unnecessary operations like clearing vectors. You don’t even need a vector in the first place. String can be split as T1 +( i iterate over this)+ T1 + T2 + T2. Just keep a pointer which tracks where the first T1 ends and you can easily form the rest substrings from this information alone. For example, if pointer is at i=3 , you know that size(T1) = 3 and size(T2) = (n/2 - i). Hope you get it.
Rabin Karp Algo