| 35 | |
| 36 | } |
| 37 | struct Hashing { |
| 38 | int n; |
| 39 | string s; // 0 - indexed |
| 40 | vector<pair<int, int>> hs; // 1 - indexed |
| 41 | Hashing() {} |
| 42 | Hashing(string _s) { |
| 43 | n = _s.size(); |
| 44 | s = _s; |
| 45 | hs.emplace_back(0, 0); |
| 46 | for (int i = 0; i < n; i++) { |
| 47 | pair<int, int> p; |
| 48 | p.first = (hs[i].first + 1LL * pw[i].first * s[i] % MOD1) % MOD1; |
| 49 | p.second = (hs[i].second + 1LL * pw[i].second * s[i] % MOD2) % MOD2; |
| 50 | hs.push_back(p); |
| 51 | } |
| 52 | } |
| 53 | pair<int, int> get_hash(int l, int r) { // 1 - indexed |
| 54 | assert(1 <= l && l <= r && r <= n); |
| 55 | pair<int, int> ans; |
| 56 | ans.first = (hs[r].first - hs[l - 1].first + MOD1) * 1LL * ipw[l - 1].first % MOD1; |
| 57 | ans.second = (hs[r].second - hs[l - 1].second + MOD2) * 1LL * ipw[l - 1].second % MOD2; |
| 58 | return ans; |
| 59 | } |
| 60 | pair<int, int> get_hash() { |
| 61 | return get_hash(1, n); |
| 62 | } |
| 63 | }; |
| 64 | int32_t main() { |
| 65 | ios_base::sync_with_stdio(0); |
| 66 | cin.tie(0); |