CHEFSHIP - Editorial

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

Can you help me in one of the situation-
To use indexing from 1, I added an extra space in front in the given string.
Let’s say my string s is - " aaaabcbbcb"

Now If I’m printing out s.substr(3,6) it is printing “aabcbb” instead of “aabc”
What is wrong in the indexing? It should take the characters from index 3rd to 6th instead it is taking characters from 3rd to 8th. Can anyone help?

Read the docs :slight_smile:

https://en.cppreference.com/w/cpp/string/basic_string/substr

1 Like

But time complexity of solution is o(n) I guess?? So why TLE??

Thanks for the help. I got it.
Everytime I try to bring back my confidence and participate in short contests it just shatter my confidence and bring it back down to ground 0. Only able to solve 1 question that too from division-2. (-_-)

1 Like

https://www.codechef.com/viewsolution/33327252

Hi. I am not able to find input for which my code is wrong. Can somebody help me?

I dont understand how collisions are checked in editorialist solution? Can someone describe it in brief?

if someone solve this problem using hashing in c++ , please share your solution

again, it had weak test cases that why it got accepted, otherwise it would have shown TLE.

I’m not checking for collisions. When we implement hashing in CP, we almost never check for collisions, as checking for collisions increases the complexity to O(N^2). We just try to create a strong hashing function so that the chances of collision are very small.

The bigger the value of MOD, the less is the chance of collision. Prime MOD ensures that the modulo cycles have a length of (MOD-1) on uniformly distributed random data.

If the test cases happen to have some strings which cause collision for our chosen base and mod values, we can add multiple hash functions to the make the chances of collision even less.

1 Like

You can refer to this for a C++ implementation of hashing.