fork download

copy

// mt19937 -> efficient pseudo-random number generator like rand()
// 70 bcz [26+26] for upper + lowercase alphabets + 10 for '0' to '9'
// and base must be greather than max. value of s[i]
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
 
// uniform_int_distribution<int> --> long long int must be used here
const int base1 = uniform_int_distribution<int>(70, MOD1 - 1)(rng);
const int base2 = uniform_int_distribution<int>(70, MOD2 - 1)(rng);
 
const int N = 5e5 + 100;
int hash1[N], hash2[N], x1[N], x2[N], inv1[N], inv2[N];
 
int mod_add(int a, int b, int mod)
{
    int tmp = (a + b) % mod;
    if (tmp < 0)
        tmp += mod;
    return tmp;
}
 
int mod_mul(int a, int b, int mod)
{
    int tmp = (a * 1LL * b) % mod;
    if (tmp < 0)
        tmp += mod;
    return tmp;
}
 
int binExpo(int a, int b, int mod)
{
    int tmp = 1;
    while (b)
    {
        if (b % 2)
            tmp = mod_mul(tmp, a, mod);
        a = mod_mul(a, a, mod);
        b /= 2;
    }
    return tmp;
}
 
void preCalc()
{
    x1[0] = x2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        x1[i] = mod_mul(x1[i - 1], base1, MOD1);
        x2[i] = mod_mul(x2[i - 1], base2, MOD2);
    }
 
    int x_inv1 = binExpo(base1, MOD1 - 2, MOD1);
    int x_inv2 = binExpo(base2, MOD2 - 2, MOD2);
    inv1[0] = inv2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        inv1[i] = mod_mul(inv1[i - 1], x_inv1, MOD1);
        inv2[i] = mod_mul(inv2[i - 1], x_inv2, MOD2);
    }
}
 
int val(char c)
{
    if (c >= 'a' && c <= 'z')
        return (c - 'a' + 1);
 
    if (c >= 'A' && c <= 'Z')
        return (c - 'A' + 27);
 
    if (c >= '0' && c <= '9')
        return (c - '0' + 53);
}
 
void build(string &s)
{
    hash1[0] = hash2[0] = val(s[0]);
    for (int i = 1; i < s.size(); i++)
    {
        hash1[i] = mod_add(hash1[i - 1], mod_mul(x1[i], val(s[i]), MOD1), MOD1);
        hash2[i] = mod_add(hash2[i - 1], mod_mul(x2[i], val(s[i]), MOD2), MOD2);
    }
}
 
// Hash for s[x....y] => x, y are index
pii getHash(int x, int y)
{
    int tmp1 = mod_add(hash1[y], (x == 0) ? 0 : -hash1[x - 1], MOD1);
    tmp1 = mod_mul(tmp1, inv1[x], MOD1);
 
    int tmp2 = mod_add(hash2[y], (x == 0) ? 0 : -hash2[x - 1], MOD2);
    tmp2 = mod_mul(tmp2, inv2[x], MOD2);
 
    // answer = {Hash1, Hash2}
    return {tmp1, tmp2};
}
 

prog.cpp:5:1: error: ‘mt19937’ does not name a type
 mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 ^~~~~~~
prog.cpp:11:19: error: ‘uniform_int_distribution’ was not declared in this scope
 const int base1 = uniform_int_distribution<int>(70, MOD1 - 1)(rng);
                   ^~~~~~~~~~~~~~~~~~~~~~~~
prog.cpp:11:44: error: expected primary-expression before ‘int’
 const int base1 = uniform_int_distribution<int>(70, MOD1 - 1)(rng);
                                            ^~~
prog.cpp:12:19: error: ‘uniform_int_distribution’ was not declared in this scope
 const int base2 = uniform_int_distribution<int>(70, MOD2 - 1)(rng);
                   ^~~~~~~~~~~~~~~~~~~~~~~~
prog.cpp:12:44: error: expected primary-expression before ‘int’
 const int base2 = uniform_int_distribution<int>(70, MOD2 - 1)(rng);
                                            ^~~
prog.cpp:77:12: error: variable or field ‘build’ declared void
 void build(string &s)
            ^~~~~~
prog.cpp:77:12: error: ‘string’ was not declared in this scope
prog.cpp:77:12: note: suggested alternative: ‘struct’
 void build(string &s)
            ^~~~~~
            struct
prog.cpp:77:20: error: ‘s’ was not declared in this scope
 void build(string &s)
                    ^
prog.cpp:88:1: error: ‘pii’ does not name a type
 pii getHash(int x, int y)
 ^~~
prog.cpp: In function ‘int val(char)’:
prog.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Standard output is empty