×

# SHIFTPAL- Editorial

Tester- Jakub Safin
Editorialist- Abhishek Pandey

EASY

# PRE-REQUISITES:

Hashing (or precisely, Identifying Palindromic Sub-string using Hashing)

# PROBLEM:

Given a string $S$ , tell how many $k-shifts$ of the string are palindromic. $k-shift$ of a string is, the string obtained on shifting every character right by $k$ positions (circularly).

# QUICK EXPLANATION:

We know that we can obtain all cyclic shifts of an array by appending an array to itself and moving the $N-sized$ window over it (to get different cyclic shifts). We use this to avoid having to cyclically shift the string again and again. After that, we use the concept of hashing to check if the strings are palindrome or not.

# EXPLANATION:

This editorial will have two parts. The first one will describe the cyclic-shift trick, and the other will describe the hashing part. It is expected that you have gone through the pre-requisites if concept of hashing is new to you. The basics of identifying palindrome string through hashing is given in the link under pre-requisites. Hence, the editorial will not explicitly describe on how to check that.

1.Cyclically Shifting Trick-

Whenever we are given the task to cyclically shift an array, or a string, we can use this trick to avoid having to actually cyclically shift the entire array again and again.

This trick says that, append the string/array to itself. Eg, if $S=abc$ then $S'=S+S=abcabc$. Now, consider the string from range $i$ to $i+N$ to obtain the $i'th$ cyclic shift of the string.

Eg-

Starting from $i=1$ $to$ $N$ ($1-based$ indexing) will give you $left$ cyclic shift of string, while decrementing from $i=N$ to $i=1$ will give you $right$ cyclic shifts of string. Now, I have one question to ask.

Why does this work? What is the foundation principle of this trick?

(Answer will be in Chef Vijju's corner)

2. Hashing the String-

You can refer to the setter's code here for the concept for now. Please note that the hash function and operations in it can vary from person to person. We will be discussing w.r.t. setter's solution first.

Now, we know the cyclic-shift trick. Using that, we can reduce the problem to "Find how many substrings (contiguous) of length $N$ are palindrome in the string $S'(=S+S)$"

If you've read the pre-requisite link, you would have got how we used the hash function of-

$h(x)= \sum_{i=0}^{i=n-1} ({101}^{i}*S_i)\%mod$ where $S_i=$ i'th character of the string.

Setter has used a similar hashing function of-

$H(X)= \sum_{i=0}^{i=n-1} ({31}^{i}*(S_i-a'))\%mod$

The steps to check for palindrome are similar. At each step, he checks for a sub-string of length $N$, modifies the hash function according to what characters are present in the $N$ length window. This step involves, w.r.t. variable $hsh$ in his solution, removal of term with lowest power of ${31}^{i}$ and adding the term ${31}^{i}*(S_i-a')$ to the function. (If you cannot make sense of this addition removal of lowest/highest power term, please refer again to link in pre-requisites). Can you try working out for $hsh2$ of setter's code? Answer will be in the tab below-

View Content

Now, what does this computation on hashing actually mean? At each step, $hsh$ is modified to represent the string shifted $left$ $(i+1)$ times, while $hsh2$ represents the reverse of string $S$ being cyclically shifted $right$ $(i+1)$ times. Compare them in the table below-

Can you actually tell the significance of ${31}^{i}$ in the hash function? As in, why should we take any constant, say $p$, and make hash function of type $H(X)=\sum_{i=0}^{i=n} {p}^{i}*S_i$. Why multiply with ${p}^{i}$ ?

The tester uses a similar concept, except that he tries to make his hash function even less error prone by introducing another prime number for $\%$ operation and making hash as $H(X)=H_1*p+H_2$ where $H_1$and $H_2$ and calculated similarly as described above. The tester explicitly uses our cyclic-shift trick. His $H$ represents the normal string $S$, which $H_i$ represents the reverse of string $S$. If hashes of these two are equal, then that means that the $N$ length sub-string, and its reverse are equal, which means that the string is palindrome. Hashes are updated in a manner, which is similar to "Sliding window", i.e. add contribution of new element, remove contribution of the oldest element (element to be removed).

A more formal description of tester's $H$ and $H_i$ function will be-

$H= \sum_{i=0}^{i=2N-1} {p}^ {i}*(S_i-a ' + 1)$ for both $H_1$ and $H_2$ and

$H_i = \sum_{i=2N-1}^{i=0} {p}^{i}*(S_i-a'+1)$, again, for both $H_{i1}$ and $H_{i2}$

In a gist, we "represent" the strings by hash function. If we find that the hash function of the string, and the reverse is equal, it means that the string is palindrome. The only thing to take care of is, your hash function must be good, and not have a high probability of error. Usually its acceptable if its probability of failing is $\le 0.001 \%$

# SOLUTION:

For immediate availability of setter and tester's solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them.

View Content
View Content

Editorialist's Solution will be put up on demand.

$Time$ $Complexity=$ $O(N)$ for setter and tester's solution.

# CHEF VIJJU'S CORNER :D

1. Foundation of cyclic-shift principle-

View Content

2. Significance of ${p}^{i}$ in hash function.

View Content

3. A view on Hash functions-

View Content

4. Regarding any doubts which might arise after reading editorial :)

View Content

5. We did have a look at hashing solution of this problem. Does a solution without hashing exist? Its your task to find out! Check out the list of successful submissions :) . (I will update this section if there I am able to find a good solution without hashing).

6. An alternate perspective for understanding hash function.

View Content

7. Tester's Notes-

View Content

8. Some related problems on hashing-

This question is marked "community wiki".

15.1k11857
accept rate: 18%

19.6k349497539

I have a doubt. If the function STRREV would have been available will this much of headache coding still be required?

(28 May, 21:06)

Nice editorials @vijju123. I wish you could be editorialist for all rated contests :)

(29 May, 00:09) 4★
2

OMG THAT WAS SO CUTEE!!

Its motivations like these that keep me going despite a few things <3

(29 May, 01:28)
1

@vijju123 nice job.

(08 Jun, 15:52) 4★

Thank you @skyhavoc :)

(08 Jun, 16:21)

 7 I solved this problem using Manacher's Algorithm. First I doubled the string and then used Manacher's Algorithm on the new string, so I only need to find out how many locations have a palindrome radius greater than length. And here is my solution: https://www.codechef.com/viewsolution/18664253 answered 27 May, 12:27 6★freeloop 344●3 accept rate: 47% A nice alternative approach :) (27 May, 15:06) cool, that's really thinking out of the box :) (28 May, 00:19) sorb19974★ I still dont understand why do we need to conider n+1 to 3*n-1 range and make increments of 2 while counting the ans ? (06 Dec, 21:18) lmao_2★
 1 If the characters are same, then the answer is equal to the length of string (e.g if s = "aaaa", answer is 4) However, can the answer ever be greater than 2 if all characters aren't same? If yes, can someone please provide an example. Thanks in advance. answered 02 Jun, 08:29 0●4 accept rate: 0% 1 Good question... (02 Jun, 09:28) 2 With "abaabaaba" the answer is 3 and with "abaabaabaabaaba" the answer is 5. Using more than three letters is also possible. With "cbabccbabccbabc" we get 3. (02 Jun, 11:09) Thank you oconnor_robert :) I am terrible at coming up with test cases. How do you do it? Did you write a program to generate cases? (02 Jun, 11:17) 2 My first thought was "ababa". That fails because the a's at either end up next to each other. From that observation I realised that we need to double the other a's. Another way to think about it is using your observation. For s = "aaaa" we get 4. If we replace each 'a' with a palindrome, we will always get at least 4. (02 Jun, 11:43) Nice work bro.. (02 Jun, 12:08) 1 "abbaabba" is also interesting and gives 4. This is different than my other examples because there are two unique palindromes that can be formed by shifting this one: "abbaabba" and "baabbaab". (02 Jun, 12:09) wow, this is amazing! Thank you again :) (02 Jun, 13:26) showing 5 of 7 show all
 0 Upd - Solved https://www.codechef.com/viewsolution/19423064 . answered 27 May, 04:29 2.2k●5●15 accept rate: 11% I didn't read through your code very carefully, but it seems that you haven't accounted for the case when subtracting the two prefix sums, or two suffix sums makes it negative. You should add MOD to it in that case. (27 May, 12:03) xrisk5★ You can check out my code here BTW I think I have written it quite clearly http://ix.io/1bvW (27 May, 12:05) xrisk5★ My method of subtraction. y=(a[1][k][2*l-i]-a[1][k][l-i]); y%=mod[k]; y=(y+mod[k])%mod[k]; (27 May, 14:36) Your code failed on sample case itself. What is the logic behind your hash function? (27 May, 15:50) Unable to format my comment. This question was my first attempt with Hash. Yes, it also fails on sample test case. m = some base. I took 26,101,1001 etc. But failed on all. There 3 for mod. All stored in modular airthmetic Hash for prefix s[0] s[0]*m+s[1] s[0]*m2+s[1]*m+s[2] s[0]*m3+s[1]*m2+s[2]*m+s[3]+.... similarly for s[2*l] s[2*l]*m+s[2*l-1] s[2*l]*m2+s[2*l-1]*m+s[2*l-2] s[2*l]*m3+s[2*l-1]*m2+s[2*l-2]*m+s[2*l-3]+.... for substring [i,j] hash value (prefix[j]-prefix[i])*(modInv(m))^i //here i found error while writing this. Will try again and get back. (27 May, 23:47) 1 I formatted it for you. Time for a comfortable reading now :D (28 May, 00:31) showing 5 of 6 show all
 0 Please tell why am I getting WA https://www.codechef.com/viewsolution/18693156 Calulating cyclic shift strings using substring and checking with palindrome using reverse() answered 29 May, 11:21 1 accept rate: 0% I think the problem is that you forgot to add new lines. If there are multiple test cases, all of the results are printed one after another on the same line. (31 May, 18:26) 1 Ahhhh.. Such lame thing costed me 30-40 mins of contest time :( Thanks @oconnor_robert :) (31 May, 22:08)
 0 This view content is excellent :D answered 31 May, 17:30 11●1 accept rate: 0% yeah it is.. :) thanks to vijju... (31 May, 18:32) I am glad you liked it :) . It was written in a rush though XD (31 May, 20:38)
 0 View Content can some one help me....thx in advance!! answered 06 Jun, 23:45 1 accept rate: 0%

why you are writing so many #define in code? what is logic behind this?

# Tester's solution

2★akash_92
0
accept rate: 0%

2

Just to make our lives easier.

(10 Jun, 10:08)
 0 @vijju123 How to deal with the problem of rounding of powers of 'p' when the power value crosses mod value? As in, when we are comparing hash and reverse hash, one hash is multiple of other hash(as given in prerequisite). But that holds true only if the power values round up at the same point for given string. e.g consider string s=abbbbbba. ns = s+s = abbbbbbaabbbbbba now if string under consideration is [2 7]. Suppose that while computing prefix array, power value rounds off at index 5. And suppose that while computing suffix array, power value rounds off at index 7. So, the hash[2 7] using prefix array CANT BE EQUAL to hash[2 7] using suffix array. How to deal with this problem? answered 27 Jun, 15:31 1★sushu 1●1 accept rate: 0% These factors depend strictly on your hash function. Check what the setter and tester have done, they did something different. They made it such that, instead of checking if $hsh$ is a multiply of $hsh2$ or not, they simply checked for $hsh1==hsh2$. Give a read to editorial if they havent. Try to get what is represented by the hash function, it will be easier to understand it. (27 Jun, 17:15) Editorial solution is expected to be put up so that we can relate with the editorial. Setter solution has been poorly explained and I couldn't get the logic behind the setter's code. Could you please tell me the logic behind setter's code? (27 Jun, 18:39) sushu1★ What do you mean by "Setter solution has been poorly explained". What did you not understand? I feel the concept is quite sufficiently explained and is easy to understand. Dry run a few iterations to understand. Editorial solution is expected to be put up so that we can relate with the editorial. -_- . The editorial explains setter's and tester's solution. What do I do then, copy paste setters code? Could you please tell me the logic behind setter's code? If such big editorial couldnt help you, I doubt my comment will. Please give more efforts before blaiming. (27 Jun, 19:05)
 0 Here is my clean hash solution : https://www.codechef.com/viewsolution/21761423 Manacher's Algorithm Solution : https://www.codechef.com/viewsolution/21760228 answered 07 Dec, 00:48 2★lmao_ 31●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,677
×621
×341
×115
×98
×39

question was seen: 3,919 times

last updated: 07 Dec, 00:48