字符串哈希

template<int N>
struct _StringHash {
    static int mod;
    static array<int, N> base;
    static vector<array<int, N>> bases;
    static bool noInit;
    vector<array<int, N>> hash;
    _StringHash(const string &str) {
        if (noInit) {
            for (int i = 0 ; i < N ; i++) {
                base[i] = getRandom();
            }
            noInit = false;
        }
        int len = str.size() + 1;
        hash.resize(len);
        if (len > int(bases.size())) {
            int k = max(1, (int) bases.size());
            bases.resize(len);
            bases[0] = {1, 1};
            for (int i = k ; i < len ; i++) {
                for (int j = 0 ; j < N ; j++) {
                    bases[i][j] = 1LL * bases[i - 1][j] * base[j] % mod;
                }
            }
        }
        for (int i = 1 ; i < len ; i++) {
            for (int j = 0 ; j < N ; j++) {
                hash[i][j] = (1LL * hash[i - 1][j] * base[j] + str[i - 1]) % mod;
            }
        }
    }
    static mt19937 rnd;
    static int getRandom() {
        return rnd() % 1000000 + 1000000;
    }
    array<int, N> get(int L, int R) {
        array<int, N> res{};
        for (int i = 0 ; i < N ; i++) {
            res[i] = (hash[R][i] - 1LL * hash[L - 1][i] * bases[R - L + 1][i] % mod + mod) % mod;
        }
        return res;
    }
}; // _StringHash
template<int N>
mt19937 _StringHash<N>::rnd(time(nullptr));
template<int N>
vector<array<int, N>> _StringHash<N>::bases;
template<int N>
array<int, N> _StringHash<N>::base{};
template<int N>
bool _StringHash<N>::noInit = true;
template<int N> // 此处修改模数, 仅支持单模数
int _StringHash<N>::mod = 1000000007;
using StringHash = _StringHash<2>; // 确定底数个数
// 定义 StringHash sh(str)
// 传入字符串必须下标从0开始
// 获取哈希值 sh.get(L, R) 区间下标以1为基础