because of the T2 (to simplify things)
you can treat T2 as T1 when the string is reversed and apply the same rule as that of T1
Why my solution is giving WA? https://www.codechef.com/viewsolution/33366047 (it passes for sample test cases, and for many custom test cases as well, well formatted)
I read about string-hashing on cp-algorithms according to which:
hash(i,j) = (hash(0,j)-hash(0,i-1))*(multiplicative modulo inverse of p^i)
and have used this in my solution.
If my WA solution is difficult to understand, I have commented my code in case here: https://ideone.com/SSDjRD
I have debugged it: here.
Check out line 32 of your code and the AC one, and I think you shall find the mistake.
1 Like
Oh! This silly mistake slipped real quick from my eyes. Thank you soo much.
1 Like
@abhishek_iiita I also tried to implement the solution using kmp algorithm, but without any extra lps array and period. Can you explain why the period is calculated for the substring?
I used the similar approach as yours for calculating the 2 lps arrays. While iterating over the original string I just checked the length of lps for two halves and if the they exceed the half lengths then I increment the count. Still getting a WA.
Here is the link to my solution - CodeChef: Practical coding for everyone
Thanks for any help 
This post was flagged by the community and is temporarily hidden.
Here is a case for which your code is failing.
1
abababaa
P.S. Your code is not covering the overlapping cases.
1 Like
Your code is not optimized that’s why you are getting TLE. It is still O(n^2). Refer this for a better understanding of the hashing in strings.
Can you explain me a little more like in which portion I have to change so my code can optimize. Any suggestion are pleased .Thanks
is there some similar question in leetcode or some other place where test cases are available. I really need to verify and improve my approach.
Below is my code. Please someone tell me what I am doing wrong in this. It is passing example set.
#include
#include <stdlib.h>
#include
#include
#include
#include <stdio.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–){
string s;
cin>>s;
int len;
int x=0;
len=s.length();
for(int i=1;i<len;i++)
{
if(s[0]==s[i])
{
string s1,s2;
s1=s.substr(0,i-1);
s2=s.substr(i,i-1);
if(s1.compare(s2)!=0)
{
continue;
}
else{
string s3,s4;
s3=s.substr(2i,((len-2i)/2)-1 );
s4=s.substr(len-(2i)+1,((len-2i)/2)-1);
if(s3.compare(s4)!=0)
{
break;
}
else{
x=x+1;
}
break;
}
}
}
if(x==1)
{
cout<<“1”<<endl;
}
else{
cout<<“0”<<endl;
}
}
return 0;
}
That modification of KMP algorithm to find non-overlapping longest prefix which is also a suffix is cool. Thanks for including that solution.
It was a good question and the story and all were interesting sir. It was my first time to get two acs in a cook-off . I felt bad in the morning when many said that my brute-force solution was not supposed to work 
! The feeling that I didn’t deserve the increase in my rating made me feel bad . So I learnt hashing as suggested in tutorial and got ac for the question in practice. I don’t think that I would have learnt hashing if my brute-force failed. Something good did come out of this sir .
Thank you.
2 Likes
Just learned String hashing. So might be a weird question. In editorialist solution :
long getHash(int l, int r){return (MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;}
}
why we are taking range of substring(r+1,l) rather than (r,l-1) ? Please explain.
Its a backward hashing that’s why loop starts from n-1 to 0 hence you find hash of getHash(l,r) = hash[l] - hash[r+1]*pow[r-l+1])%MOD this way.
For forward hashing we could have used getHash(l,r) = hash[r] - (hash[l-1]*power[r-l+1]%MOD) this way.
I have tried using forward hashing still I have to use the range(l,r+1) otherwise wrong answer. Here:- CodeChef: Practical coding for everyone
setter and tester sir can explain there solutions. Please sir.
i have also used LPS(Prefix sum technique) as setter solution but i did not get it! why @rishup_nitdgp used the (len*2>(i+1)). could you please explain me the little bit!
1 Like