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