哈希(Hash)算法模板

const ull MOD = 998244353;
typedef unsigned long long ull;
ull h[MAXN], p[MAXN];
inline ull hash(string s) {  //求哈希值
    static const ull BASE = 131;
    ull res = 0;
    int len = s.length();
    for(int i = 0; i < len; i++) {
        p[i] = p[i - 1] * BASE;
        h[i] = (h[i - 1] * p[i] + ull(s[i])) % MOD;
    }
    return h[len - 1];
}

inline ull sub_hash(int l, int r) { //子串哈希值
    return ((h[r] - h[l] * p[r - l + 1]) % MOD + MOD) % MOD;
}

使用时为了防止哈希冲突产生影响，一般使用模数不同的双哈希判断。