PROBLEM LINK:Setter Hasan Jaddouh DIFFICULTY:EASY PREREQUISITES:Hashing (or precisely, Identifying Palindromic Substring using Hashing) PROBLEM:Given a string $S$ , tell how many $kshifts$ of the string are palindromic. $kshift$ 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 $Nsized$ 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 cyclicshift trick, and the other will describe the hashing part. It is expected that you have gone through the prerequisites if concept of hashing is new to you. The basics of identifying palindrome string through hashing is given in the link under prerequisites. 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$ ($1based$ 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 cyclicshift 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 prerequisite link, you would have got how we used the hash function of $h(x)= \sum_{i=0}^{i=n1} ({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=n1} ({31}^{i}*(S_i`a'))\%mod$ The steps to check for palindrome are similar. At each step, he checks for a substring 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 prerequisites). Can you try working out for $hsh2$ of setter's code? Answer will be in the tab below 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 cyclicshift 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 substring, 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=2N1} {p}^ {i}*(S_i`a ' + 1)$ for both $H_1$ and $H_2$ and $H_i = \sum_{i=2N1}^{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. Editorialist's Solution will be put up on demand. $Time$ $Complexity=$ $O(N)$ for setter and tester's solution. CHEF VIJJU'S CORNER :D1. Foundation of cyclicshift principle 2. Significance of ${p}^{i}$ in hash function. 3. A view on Hash functions 4. Regarding any doubts which might arise after reading editorial :) 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. 7. Tester's Notes 8. Some related problems on hashing
This question is marked "community wiki".
asked 26 May, 04:05

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
A nice alternative approach :)
(27 May, 15:06)
cool, that's really thinking out of the box :)
(28 May, 00:19)
I still dont understand why do we need to conider n+1 to 3*n1 range and make increments of 2 while counting the ans ?
(06 Dec, 21:18)

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
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

Please help me https://www.codechef.com/viewsolution/18671686 . https://www.codechef.com/viewsolution/18671710 . . Upd  Solved https://www.codechef.com/viewsolution/19423064 . answered 27 May, 04:29
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)
You can check out my code here BTW I think I have written it quite clearly http://ix.io/1bvW
(27 May, 12:05)
My method of subtraction. y=(a[1][k][2*li]a[1][k][li]); 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.
for substring [i,j]
(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

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
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 3040 mins of contest time :( Thanks @oconnor_robert :)
(31 May, 22:08)

why you are writing so many #define in code? what is logic behind this? Tester's solutionanswered 09 Jun, 01:39

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

I have a doubt. If the function STRREV would have been available will this much of headache coding still be required?
Nice editorials @vijju123. I wish you could be editorialist for all rated contests :)
OMG THAT WAS SO CUTEE!!
Its motivations like these that keep me going despite a few things <3
@vijju123 nice job.
Thank you @skyhavoc :)