RollingHash

code:cpp

const ulong MASK30 = (1UL << 30) - 1;

const ulong MASK31 = (1UL << 31) - 1;

const ulong MOD = (1UL << 61) - 1;

const ulong MASK61 = MOD;

ulong CalcMod(ulong x)

{

ulong xu = x >> 61;

ulong xd = x & MASK61;

ulong res = xu + xd;

if (res >= MOD) res -= MOD;

return res;

}

ulong Mul(ulong a, ulong b)

{

ulong au = a >> 31;

ulong ad = a & MASK31;

ulong bu = b >> 31;

ulong bd = b & MASK31;

ulong mid = ad * bu + au * bd;

ulong midu = mid >> 30;

ulong midd = mid & MASK30;

return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);

}

template< ulong MOD >

struct RollingHash {

vector< ulong > hashed, power;

RollingHash(const string &s, ulong base = 10007) {

int sz = (int) s.size();

hashed.assign(sz + 1, 0);

power.assign(sz + 1, 0);

for(int i = 0; i < sz; i++) {

}

}

ulong get(int l, int r) const {

if(l==r)return 0;

if(ret >= MOD) ret -= MOD;

return ret;

}

ulong connect(ulong h1, int h2, int h2len) const {

if(ret >= MOD) ret -= MOD;

return ret;

}

};

using RH = RollingHash<MOD>;