1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| const long long base = 131; const long long mod1 = 805306457, mod2 = 1610612741; using Hash = std::array<long long, 2>;
struct HASH { int n; std::string s; std::vector<Hash> hash; std::vector<Hash> p;
HASH() {} HASH(std::string s) { init(s); }
void init(std::string a) { this -> s = a; n = s.size(); s = " " + s; hash.assign(n + 1, {0, 0}); p.assign(n + 1, {0, 0}); for (int i = 1; i <= n; i++) { hash[i][0] = (base * hash[i - 1][0] + (long long)s[i]) % mod1; hash[i][1] = (base * hash[i - 1][1] + (long long)s[i]) % mod2; } p[0] = {1, 1}; for (int i = 1; i <= n; i++) { p[i][0] = p[i - 1][0] * base % mod1; p[i][1] = p[i - 1][1] * base % mod2; } }
Hash get(int l, int r) { l += 1, r += 1; Hash res; res[0] = ((hash[r][0] - hash[l - 1][0] * p[r - l + 1][0] % mod1) % mod1 + mod1) % mod1; res[1] = ((hash[r][1] - hash[l - 1][1] * p[r - l + 1][1] % mod2) % mod2 + mod2) % mod2; return res; }
};
|