How to implement this chef and chefina question using hashing of strings? I’m unable to understand the code of tester and setter.
I mean I’ll first iterate over the even indices of given string s. Then I’ll create 4 strings T1, T2, T3 and T4 using substr() function. and then I’ll check their hash value if hash_value(T1)==hash_value(T2) && hash_value(T3)==hash_value(T4) then increment the answer.
Is this the optimized approach? If not then how to do this?
@akashbhalotia While using hashing , can we always assume the strings match if the hash values are equal?
codeforces is better than codechef. cause it doesn’t pass solution with higher complexities.
@admin But some of us didn’t wrote brute force as even there was no partial marking and ended up the contest while thinking for an optimized solution.
A very heavy loss in my rating(-108).That’s not fair to be honest
can you please explain setter’s approach?
i know KMP algorithm is used here but didn’t able to get how?
thanks for reply, i get it now
Syntax is substr( starting index , length );
I’m basically using two lps, lps1 is with overlapping and lps2 is without overlapping. Ips1 is the same as used in KMP. Now, see how can we construct lps2 with the help of lps1. We know that we are moving both the i and len with 1 increment. When we first encountor the overlapping then is should involve only one charactor overlap i.e. for any position i, if there is overlap then it should be such that substring 1 to k is equal to substring k to i. We can replace the len in this case with the length recorded in lps1 for len-1.
You can also find the video Editorials for the 3rd problem of the Cook Off which is Impressing Chefina.
Impressing Chefina
The Video editorial for the second problem is also uploaded soon.
@akashbhalotia Can you explain the implementation of getHash(int l, int r) function in your code. I am not able to follow it. What the function is doing. I understood the precomputation of hash value for the whole string but just not getting the getHash function.
are the test cases strong for the practice section ?
you all are using a lot of algorithms for string matching and everything But, can u all please check out this 9 line code solution. This is submitted after some hours of contest when the problems are shifted to practice section.
Thank You for such an explanation. I didn’t see it earlier. Can we implement the hash for prefix sums and then change getHash accordingly ? Will it work.
Yes, it will work.
Ok boomer.
@akashbhalotia pleaseeeeee explain these two lines
hashs[i]=(1LL * hashs[i+1] * P + s[i] - ‘a’ + 1) % MOD;
pows[n-i]=(1LL * pows[n-i-1] * P) % MOD;
and this line too
int ans=hashs[l] + MOD - (1LL*hashs[r+1]*pows[r-l+1])%MOD;
???