Can u GIve any Example where it may fails?
what i thought if S=p2 + p3 if there is any way to split S into p1 + p4 then it will validate the conditions
It is correct. You are still doing the same thing but in a different way.
I am trying to solve this question using KMP algorithm but I am getting runtime error.
Can any one help me to locate where am I committing the mistake?
Here’s my code: CodeChef: Practical coding for everyone
thanks in advance!!
i have used hashing here .when i submit my solution it is giving me wrong answer
Thanks @rishup_nitdgp for such a good question and also @akashbhalotia for such a great editorial !!
My unnecessary story for the question :
I finally solved this problem and I believe that I have got a basic understanding of string hashing. I still am having a few doubts regarding this topic - string hashing.
Firstly I was checking for collisions in my code so I got TLE. So my hope for solving this question got smashed
.
So basically I want to know whether or not should we check for collision and if yes then when should we and how can one make checking collisions more effective ?
Also can anyone please answer this question also ? It’s regarding the Chef Impress question in this month’s cook off. It will be great help for beginners like me.
2 Likes
@rishup_nitdgp @akashbhalotia hello sir after reading your editorial I tried to do this question but it got TLE can you please have a look at my solution and explain me where I do something wrong. Any suggestions are welcome sir.
KIndly reply after seeing the comment. It will help me to improve me.
1 Like
Refer to this link for understanding the string hashing and how to decrease the probability of collisions.
1 Like
I used hashing creates a hash function and if the value of pairs of the hash function is equal then it is a match.
can someone explain to me why I’m getting TLE?
@rishup_nitdgp @everule1 @akashbhalotia Please have a look sir
dd={}
modulo=10**9+7
for i in range(97,123):
dd[chr(i)]=i-97+1
def search(pattern,text):
n=len(pattern)
c=0
e=0
for j in range(n):
a=dd[pattern[j]]
b=dd[text[j]]
c+=(a*(10**(n-j-1)))%modulo
e+=(b*(10**(n-j-1)))%modulo
return c==e
for _ in range(int(input())):
s=input()
n=len(s)
co=0
if n<4:
print("0")
else:
for i in range(2,n,2):
a=s[:i//2]
b=s[i//2:i]
c=s[i:(i+n)//2]
d=s[(i+n)//2:]
if search(a,b) and search(c,d):
co+=1
print(co)
Thanks !!
I got it now 
1 Like
Getting TLE for following code, used KMP string matching.
#include<bits/stdc++.h>
using namespace std;
void computeprefix(int pref[], string P)
{
pref[0]=0;
int k=0, m=P.length();
for(int i=1;i<m;i++)
{
//recursively get longest proper prefix and suffix in the existing longest proper substring
//which is already a prefix and suffix
while(k>0 && (P[k]!=P[i]))
k=pref[k];
if(P[k] == P[i])
k=k+1;
pref[i]=k;
}
// cout << "prefix function\n";
// for(int i=0;i<m;i++)
// cout << pref[i] << " ";
// cout << endl;
}
int findoccurence(string T, string P, int pref[], int st)
{
int n, m; n=T.length(); m=P.length();
int q=0;
for(int i=st;i<n;i++)
{
while(q>0 && T[i] != P[q])
q=pref[q];
if(T[i] == P[q])
q++;
if(q == m)
{
return i-(m-1);
// cout << "Pattern matches at: " << i-(m-1) << " " << endl;
// q=pref[q-1]; //for futher remaining text
}
// cout << i << endl;
}
return -1;
}
bool check(string T, string P, int pref[], int st, int n, int m)
{
if(st == n)
return false;
int l=n-st;
if(l%2 == 1)
return false;
int sz=(n-st)/2;
int ind1=st, ind2=st+sz;
for(int i=0;i<sz;i++)
{
if(T[ind1] != T[ind2])
return false;
ind1++;
ind2++;
}
return true;
}
int main()
{
int t; cin >> t;
while(t--)
{
string T, P; cin >> T;
int n, m, cnt=0;
n=T.length();
P="";
P=P+T[0];
set< pair<int, int> > s;
for(int i=1;i<=n;)
{
m=i;
int pref[m]; //prefix array for out query
computeprefix(pref, P);
int val=findoccurence(T, P, pref, i);
// cout << val << " " << i << " " << P << endl;
if(val == i && check(T, P, pref, val+i, n, m))
cnt++;
if(i == n)
break;
P=P+T[i];
i++;
}
cout << cnt << endl;
}
return 0;
}can any one tell what is wrong with my solution please
https://www.codechef.com/viewsolution/33351237
@abhishek_iita can you please explain why did we create the lps array of reversed string?
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