【字符串】字符串多项式哈希

struct StringHashing {

    static const int MAXN = 1000005;

    int n;
    int bse[3] = {13, 1331, 2333};
    int mod[3] = {998244353, 1000000007, 1000000009};
    int bsk[MAXN][3], hsh1[MAXN][3], hsh2[MAXN][3];

    void Init(char *s) {
        n = strlen(s + 1);
        for(int t = 0; t < 3; ++t) {
            bsk[0][t] = 1, hsh1[0][t] = 0, hsh2[n + 1][t] = 0;
            for(int i = 1; i <= n; ++i) {
                bsk[i][t] = (1LL * bsk[i - 1][t] * bse[t]) % mod[t];
                hsh1[i][t] = (1LL * hsh1[i - 1][t] * bse[t] + s[i]) % mod[t];
                hsh2[n + 1 - i][t] = (1LL * hsh2[n + 1 - i + 1][t] * bse[t] + s[n + 1 - i]) % mod[t];
            }
        }
    }

    int HashCode1(int L, int R, int t) {
        int res = (hsh1[R][t] - 1LL * hsh1[L - 1][t] * bsk[R - L + 1][t]) % mod[t];
        res += (res < 0) ? mod[t] : 0;
        return res;
    }

    int HashCode2(int L, int R, int t) {
        int res = (hsh2[L][t] - 1LL * hsh2[R + 1][t] * bsk[R - L + 1][t]) % mod[t];
        res += (res < 0) ? mod[t] : 0;
        return res;
    }

    bool isEqual(int L1, int R1, int L2, int R2) {
        if(L1 < 1 || R1 > n || L2 < 1 || R2 > n)
            return 0;
        if(L1 > R1 && L2 > R2)
            return 1;
        for(int t = 0; t < 3; ++t) {
            if(HashCode1(L1, R1, t) != HashCode1(L2, R2, t))
                return 0;
        }
        return 1;
    }

    bool isReverseEqual(int L1, int R1, int L2, int R2) {
        if(L1 < 1 || R1 > n || L2 < 1 || R2 > n)
            return 0;
        if(L1 > R1 && L2 > R2)
            return 1;
        for(int t = 0; t < 3; ++t) {
            if(HashCode1(L1, R1, t) != HashCode2(L2, R2, t))
                return 0;
        }
        return 1;
    }

} sh;

【字符串】字符串多项式哈希

原文：https://www.cnblogs.com/purinliang/p/14060672.html