Thank you so much. I still don’t fully understand because I am not very familiar with the topic, but I really appreciate the time that you took to write out the response. Thank you so much.
Time complexity is O(n).
Approach:
- I used hash prefix sums one from the left and another one from the right.
- First Iterate from L to R, then R to L.
- while iterating from left to right; check if the other half of current substring has the same hash, If yes, check if they are equal using substring matching, Increment left Array on that position and similarly, for right Array while iterating from right to left.
- To get Substring in O(1), I used string_view, it’s a new feature in C++17. (WTF! right ?, I know, It’s crazy).
- Finally, Iterate through indices and Compute answer from the left and right arrays which denotes if the ith position can result in solution from left and from right respectively.
Checkout the solution:
#include <bits/stdc++.h>
#define pi pair<int,int>
#define EPS 1e-9
#define ll long long int
#define pii pair<long long,long long>
#define f(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define rf(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
#define PI 3.14159265
#define ff first
#define ss second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define debug(x) cout << #x << " = " << x << endl
#define INF 1000000009
#define mod 1000000007
using namespace std;
int t,n;
string s;
int main()
{
cin>>t;
while(t--)
{
cin>>s;
n = s.size();
string_view sv(s.c_str(), n);
vector<int> hash1(n+1, 0), left(n+1, 0), right(n+1, 0), hash2(n+1, 0);
unordered_map<int,int> m;
hash1[0] = s[0]-'a'+1;
m[hash1[0]] = 1;
left[0] = 0;
for (int i=1;i<n-2;i++) {
hash1[i] = hash1[i-1] + s[i]-'a'+1;
if (m.count(hash1[i]>>1) && sv.substr(0, i/2+i%2) == sv.substr(i/2+i%2, i/2+1)) left[i]++;
m[hash1[i]] = 1;
}
m.clear();
hash2[n-1] = s[n-1]-'a'+1;
m[hash2[n-1]] = 1;
right[n-1] = 0;
for (int i=n-2, j=1;i>=2;i--, j++) {
hash2[i] = hash2[i+1] + s[i]-'a'+1;
if (m.count(hash2[i]>>1) && sv.substr(i, j/2+1) == sv.substr(i+j/2+1)) right[i]++;
m[hash2[i]] = 1;
}
int ans = 0, l,r;
for (int i=0;i<n;i++) {
ans += left[i]*right[i+1];
}
cout<<ans<<"\n";
}
return 0;
}
Happy Coding!
2 Likes
more specifically if i==n-1 then hash[i+1],i.e hash[n], then what will be the value of hash[n]?
https://www.codechef.com/viewsolution/33301822
Why this solution doesn’t get accepted and showing tle,Before I was using the erase function but I read it takes O(n) time to delete a front element from a string so I reversed the string (by making the string in reverse order ,and not using reverse) and check so now the last element has to be deleted,I just wonder I used pop-back()
It used O(1) time,
Can anyone ple. tell the problem of running it.
And what’s the complexity of string concatenation 
?
Hey, how come this solution was accepted?
def letsdp(s):
c=0
for i in range(2,len(s)-1):
x=s[:i]
y=s[i:]
if len(x)&1==0 and len(y)&1==0:
x1 = x[:len(x)>>1]
x2 = x[len(x)>>1:]
y1 = y[:len(y)>>1]
y2 = y[len(y)>>1:]
# print(x1,x2,y1,y2)
if x1==x2 and y1==y2:
c+=1
return c
for _ in range(int(input())):
n=input()
counts = letsdp(n)
print(counts)
I tried to implement rolling hash using prefix hash of string instead of suffix with the help of this But I’m getting WA, Can you help what’s wrong in my approach-
ll MOD = 1e9 + 7;
#define max 100002
int p = 31;
ll hashfunction[max], power[max];
void precompute(string s, int n){
hashfunction[0] = (s[0]-'a'+1);
power[0] = 1;
ll pow = p;
for(int i=1; i<n; i++){
power[i] = pow;
hashfunction[i] = (hashfunction[i-1] + (s[i]-'a'+1)*pow)%MOD;
pow = (pow * p)%MOD;
}
}
ll getHash(int l, int r){
if(l==0) return (MOD + hashfunction[r] - (hashfunction[l]*power[r-l])%MOD)%MOD;
return (MOD + hashfunction[r] - (hashfunction[l-1]*power[r-l])%MOD)%MOD;
}
Please help!
It’s an o(n^2) soln string concatenation is linear complexity o(n)
I have used Rolling hash algorithm, but I am still getting TLE. Please help 
link: CodeChef: Practical coding for everyone
my code:
#include <chrono>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <assert.h>
#include<unordered_map>
const double Epsilon = 4.94065645841247E-324;
const long double PI = 3.14159265358979323846;
const long long int MOD = 1000000007;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define dbg(x) cerr << #x << " is " << x << endl;
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define setall(a,v) memset((a),v,(sizeof(a)))
using namespace std;
clock_t beg = clock();
// #include <iterator>
// template<typename T>
// void printVector(const T& t) {
// std::copy(t.cbegin(), t.cend(), std::ostream_iterator<typename T::value_type>(std::cout, ", "));
// }
// template<typename T>
// void printVectorInVector(const T& t) {
// std::for_each(t.cbegin(), t.cend(), printVector<typename T::value_type>);
// }
/*----------------------------MAIN HERE----------------------------------*/
class Hasher{
public:
vector<ull> h;
vector<ull> base_power;
ull mod;
Hasher(string s, ull base, ull modp){
int len = s.size();
this->mod = modp;
h.resize(len+1);
base_power.resize(len+1);
h[len]=0;
for (int i = len-1; i>=0; i--)
{
h[i] = ((h[i+1] * base)%mod + (s[i]-'a'+1)) % mod;
}
base_power[0]=1;
for (int i = 1; i < len+1; i++)
{
base_power[i] = (base_power[i-1]*base) % mod;
}
}
ull getHash(int i, int j){
return (h[i] - (h[j+1] * base_power[j-i+1]) % mod ) % mod;
}
};
bool issame(string s, int i, int j, Hasher hasher){
ull a,b;
int n = s.size();
int len = j-i;
if((j+len-1)>n-1) return false; // b part not complete
// a = hm[j-1] - ((i>0)*hm[i-1]);
// b = hm[j+len] - hm[j-1];
a = hasher.getHash(i,j-1);
b = hasher.getHash(j,j+len-1);
// cout<<"\n"<<s.substr(i,len)<<" == "<<s.substr(j,len)<<" : "<<(a==b)<<"\n";
return a==b;
// for (int k = i, l=j ; k < j; k++,l++)
// {
// if(s[k]!=s[l]) return false;
// }
// return true;
}
ll solve(string str){
int len = str.size();
int s = str[0];
vector<int> sv;
ll count=0;
for (int i = 1; i < len/2; i++) {
if(str[i]==s){
sv.push_back(i);
}
// if(str[i]==e && i>(len/2)){
// ev.push_back(i);
// }
}
Hasher hasher(str, 31, (1e+9)+7);
// cout<<" \nhash[";
// for (int i = 0; i < len; i++) {
// cout<<hasher.getHash(i,len-1)<<" ";
// }
// cout<<"]\n";
// cout<<"\n [1,1] : "<<hasher(str.substr(1,1))<<" | "<<hm[1]-hm[0];
// cout<<"\n [2,2] : "<<hasher(str.substr(2,1))<<" | "<<hm[2]-hm[1];
// cout<<issame(str, 0, 2, hasher);
// exit(-1);
// if(s<=e){
for (auto &candx : sv)
{
int y1 = 2*candx;
int y2 = len - 2*candx + 1;
// cout<<" candx:"<<candx<<", candy: "<<candy<<"\n";
bool truth = issame(str, 0, candx, hasher) && issame(str, y1, y2, hasher);
if(truth) count++;
}
return count;
}
int main() {
fastio; //warning: with this, do not use cin+scanf or cout+printf !
int t=1;
cin>>t;
int ti=0;
while(ti++<t){
string s;
cin>>s;
cout<<solve(s)<<"\n";
}
cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
return 0;
}
isn’t It sufficient to just check P1 + P4 == P2 + p3
This solution Passed but I’m not sure if it is correct
here is My solution :CodeChef: Practical coding for everyone
Can somebody explain how to do this problem using KMP ?
1 Like
i just want to know one thing!! i am desperatly trying to get c++17 but there is some bug can you plz help me out like just tell me the steps and i will blindly follow bcz im very frustated, plz help me to get c++17
Errors while compiling
d:\cpp\helloworld\H_Binary_Median.cpp:45:5: note: ‘std::string_view’ is only available from C++17 onwards
getting this error on vs code
Check the Setter’s solution. It’s done using KMP
Thanks rishup_nitdgp for the quick response usually many authors are not that active and not listen’s to everyone’s query.
Thanks for ur help.
by the way i tried to submit same question using KMP’s lps array but slightly different approach i.e,
i compute only standard LPS array and then used that to find period of a substring (period here denotes after how many minimum characters it is being repeated)
period = lenOfSubstring - lps[lenOfSubstring-1]
for ex -
aabcaabcaabc
aabc|aabc|aabc
period of this string is 4
aabcaabcaa
aabc|aabc|aa
period of this string is also 4
i used this info to find out if half of of substring is divisible by period or not , if yes that means it is of form T1 + T1.
link to solution - CodeChef: Practical coding for everyone
Hope if it helps someone.
Thanks,
2 Likes
Actually I am using code similar to setter. Here I used ‘‘if((2lps1[0][i] >= (i+1)) && (2lps1[1][n-i-2] >= (n-i-1)))’’ condition and incremented my count and did not calculated lps2. Can you please give me an example when my condition would not increment the count.
@rishup_nitdgp is there any need for the two lps array.Can’t we do it in a single lps array i.e one for the given string and one for the reverse one
Thankyou! 
why there are some solutions in hashing that are working without using modulus in hashing…why there is no integer overflow
I don’t know how can this solution pass the test cases. P1 + P4 and P2 + P3 can be different because what matters is P1==P2 and P3==P4.