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.
Good question…
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.
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?
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.
Nice work bro…
“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”.
wow, this is amazing! Thank you again
#include
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
lli pow2(lli p){
return 1 << p;
}
int main()
{
lli t,n;string s;
cin>>t;lli count=0;
for(lli tt=0;tt<t;tt++)
{
cin>>s;
n=s.length();
s=s+s;
count=0;
lli sum1=0,sum2=0;int k=2;
for(lli i=0;i<n;i++)
{
sum1+=(s[i]-‘a’+1)*(lli)(pow2(i));
sum2+=(s[i]-'a'+1)*(lli)(pow2(n-1-i));
}
if(sum1==sum2)count++;
for(lli i=1;i<n;i++)
{
lli j=i+n-1;
sum1-=(s[i-1]-'a'+1);
sum1/=k;
sum1+=(s[j]-'a'+1)*(lli)(pow2(n-1));
sum2-=(s[i-1]-'a'+1)*(lli)(pow2(n-1));
sum2*=k;
sum2+=(s[j]-'a'+1);
if(sum1==sum2)count++;
}
cout<<count<<"\n";
}
return 0;
}
can some one help me…thx in advance!!
Just to make our lives easier.
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?
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.
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?
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.
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 ?
Here is my clean hash solution : https://www.codechef.com/viewsolution/21761423
Manacher’s Algorithm Solution : https://www.codechef.com/viewsolution/21760228