CHEFSHIP - Editorial

[aadiupadhyay]

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

[vin_04]

@rishup_nitdgp Got it! Thanks

[sirdan]

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.

[tilak_40]

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

[zephyr_23]

That modification of KMP algorithm to find non-overlapping longest prefix which is also a suffix is cool. Thanks for including that solution.

[krishna_kc]

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.

[satyam_656]

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.

[pakalupapito]

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.

[satyam_656]

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

[anon24016312]

why am i getting TLE in my code :
MY CODE
any help and insight would be helpful.
Thank you.

[yogesh2000]

setter and tester sir can explain there solutions. Please sir.

[qwerty87]

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!

[rishup_nitdgp]

It is for avoid overlapping. I explained it here:

CHEFSHIP - Editorial

I’m basically using two lps, lps1 is with overlapping and lps2 is without overlapping. Ips1 is the same as used in KMP. Now, see how can we construct lps2 with the help of lps1. We know that we are moving both the i and len with 1 increment. When we first encountor the overlapping then is should involve only one charactor overlap i.e. for any position i, if there is overlap then it should be such that substring 1 to k is equal to substring k to i. We can replace the len in this case with the len…

[abhi_dtu2014]

@pastor Read about gcc compilers and try to find which gcc is your vs code running on. I mostly use ideone but seems like it still doesn’t support c++17. I used code and compile from codechef only.

[anshuman126]

can you please provide the cpp code by using hashing

[aayush_84719]

For each iteration you are calculating the hashValue in O(n), thus making your overall complexity O(n*n) which will surely timeout. You need to do some preCalculation as you are calculating the same stuff again and again.
Have a look : CodeChef: Practical coding for everyone

[ajaygupta007]

in kmp solution of setter why use 2 keys(0,1).is it can using only two 1d-array?
my question is why prefix function is calculated for reverse of array

[pastor]

i found a blog and now on i have c++17 running fine on codeblocks with the same mingw compiler but still no help in vs code i don’t know how to manipulate json in vscode and i guess thats why it is working

[harsh_joeyit]

I have used the KMP approach. It is getting a WA
Can anybody find mistake in my CODE

[iit_yt_28]

Sir can you explain what do you mean by overlapping length ? PLz