Hello codeforces community,
I was trying to solve the problem : https://www.spoj.com/problems/ADAPHOTO/
But I am getting TLE on it
Here is my code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x...) { cout << "(" << #x << ")" << " = ( "; PRINT(x); }
template <typename T1> void PRINT(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void PRINT(T1 t1, T2... t2) { cout << t1 << " , "; PRINT(t2...); }
#define all(v) (v).begin(), (v).end()
//(data type to be stored (pair,long long,string,vector),"null_type"(specifically used for set),comparator,underlying tree,class denoting the policy for updating node invaralong longs)
typedef tree < pair<long long,long long>, null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update > pbds;
void solve();
#define MAXLEN 1000010
constexpr uint64_t mod = (1ULL << 61) - 1;
const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);
uint64_t base_pow[MAXLEN];
int64_t modmul(uint64_t a, uint64_t b){
uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & mod) + (ret >> 61);
ret = (ret & mod) + (ret >> 61);
return ret - 1;
}
void init(){
base_pow[0] = 1;
for (int i = 1; i < MAXLEN; i++){
base_pow[i] = modmul(base_pow[i - 1], base);
}
}
struct chash {
const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
static unsigned long long hash_f(unsigned long long x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
int operator()(int x) const { return hash_f(x)^RANDOM; }
};
struct PolyHash{
/// Remove suff vector and usage if reverse hash is not required for more speed
vector<int64_t> pref;
PolyHash() {}
template <typename T>
PolyHash(const vector<T>& ar){
if (!base_pow[0]) init();
int n = ar.size();
pref.resize(n + 3, 0);
for (int i = 1; i <= n; i++){
pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
if (pref[i] >= mod) pref[i] -= mod;
}
}
/*https://usaco.guide/gold/string-hashing?lang=cpp*/
/* pref[r+1]=( p^r+1 + a[0]*p^(r) + a[1]*p^(r-1) + a[2]*p^(r-2) + ..+ a[l-1]*p^((r+1)-(l-1+1))+a[l]*p^((r+1)-(l+1)) .. a[r-1]*p + a[r] )
pref[l]=( p^l + a[0]*p^(l-1) + a[1]*p^(l-2) + a[2]*p^(l-3) + ...a[l-2]*p + a[l-1])
p^(r-l+1)*pref[l] = ( a[0]*p^(r) + a[1]*p^(r-1) +.... + a[l-1]*p^(r-l+1) )
pref[r+1]-(p^(r-l+1))*pref[l]=a[l]*p^(r-l)+ a[l+1]*p^(r-l-1)+.... + a[r-1]*p + a[r]
*/
PolyHash(const char* str)
: PolyHash(vector<char> (str, str + strlen(str))) {}
uint64_t get_hash(int l, int r){
int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
return h < 0 ? h + mod : h;
}
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.setf(ios::fixed);
cout.precision(10);
solve();
}
void solve()
{
string a;
cin>>a;
string b;
cin>>b;
int n1=a.length();
int n2=b.length();
const char *c1=a.c_str();
const char *c2=b.c_str();
PolyHash s1(c1);
PolyHash s2(c2);
int low=1;
int res=0;
int high=min(n1,n2);
while(low<=high)
{
int mid=(low+high)/2;
cc_hash_table<uint64_t,uint64_t,chash>mp;
int flag=0;
// unordered_map<long long,long long>mp2;
for(int i=0;i+mid-1<n1;i++)
{
uint64_t x=s1.get_hash(i,i+mid-1);
// debug(x,mid,1);
if(mp.find(x)==mp.end())
mp[x]++;
}
for(int i=0;i+mid-1<n2;i++)
{
uint64_t x=s2.get_hash(i,i+mid-1);
// debug(x,mid,2);
if(mp[x]>0)
{
flag=1;
break;
}
}
if(flag)
{
// cout<<mid<<endl;
res=mid;
low=mid+1;
}
else
{
high=mid-1;
}
}
cout<<res<<endl;
}
any help would be appreciated. Thank you in advance!
