标准解法

双哈希+大质数取模

用途

O(1)求字符串以及子串

tip

  1. 进制数尽量使用233333，1313131等较大数，不容易被卡
  2. 取模使用孪生双素数和

Hash公式

1
hash[i] = hash[i-1] * base + s[i] - '0'（字母同理）

获取子串的Hash

对于 的字符串子串，对应的区间Hash值为：
    (% mod + mod ) % mod
其中，需要率先预处理pw数组(base的指数)

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
#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
char s[200010];
i64 Hash1[200010], Hash2[200010], pw1[200010],pw2[200010];
const int base1 = 1313131, base2 = 233333;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
signed main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, l, r;cin >> n >> l >> r;
    cin >> s + 1 ;
    int len = strlen(s + 1);
    pw1[0] = pw2[0] = 1;
    Hash1[0] = Hash2[0] = 0;
    for (int i = 1; i <= len; i++){
        Hash1[i] = (Hash1[i - 1] * base1 % p1 + (s[i] - 'a' + 1)) % p1;
        Hash2[i] = (Hash2[i - 1] * base2 % p2 + (s[i] - 'a' + 1)) % p2;
        pw1[i] = (pw1[i - 1] * base1) % p1;
        pw2[i] = (pw2[i - 1] * base2) % p2;
    }
    auto getHash1 = [&](int a, int b) -> i64
    {
        return (Hash1[b] - Hash1[a - 1] * pw1[b - a + 1] % p1 + p1) % p1;
    };
    auto getHash2 = [&](int a, int b) -> i64
    {
        return (Hash2[b] - Hash2[a - 1] * pw2[b - a + 1] % p2 + p2) % p2;
    };
    return 0;
}