2013-team4/code/poly-hash

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
多项式哈希

如长度为 5 的字符串 s：
h[5] = 0
h[4] = s[4]
h[3] = s[4]x^1 + s[3]
h[2] = s[4]x^2 + s[3]x^1 + s[2]
h[1] = s[4]x^3 + s[3]x^2 + s[2]x^1 + s[1]
h[0] = s[4]x^4 + s[3]x^3 + s[2]x^2 + s[1]x^1 + s[0]

从 i 开始，长度为 L 的字符串哈希值为：
H(i, L) = h[i] - h[i + L]x^L

二维也可以使用，注意两个方向选择不同的 x 值
}}}
{{{
typedef char DATA;
typedef unsigned long long ULL;
const int MAXL = 1004;

struct hash{
    int x;
    ULL xp[MAXL];
    void init(int x){
        this->x = x;
        xp[0] = 1;
        for(int i = 1; i < MAXL; i++)
            xp[i] = xp[i - 1] * x;
    }
    void cal(DATA *s, int l, ULL *f){
        f[l] = 0;
        for(int i = l - 1; i >= 0; i--)
            f[i] = f[i + 1] * x + s[i];
    }
    ULL get(int i, int l, ULL *f){
        return f[i] - f[i + l] * xp[l];
    }
};
}}}

多项式哈希
如长度为 5 的字符串 s：
h[5] = 0
h[4] = s[4]
h[3] = s[4]x^1 + s[3]
h[2] = s[4]x^2 + s[3]x^1 + s[2]
h[1] = s[4]x^3 + s[3]x^2 + s[2]x^1 + s[1]
h[0] = s[4]x^4 + s[3]x^3 + s[2]x^2 + s[1]x^1 + s[0]
从 i 开始，长度为 L 的字符串哈希值为：
H(i, L) = h[i] - h[i + L]x^L
二维也可以使用，注意两个方向选择不同的 x 值

typedef char DATA;
typedef unsigned long long ULL;
const int MAXL = 1004;
struct hash{
    int x;
    ULL xp[MAXL];
    void init(int x){
        this->x = x;
        xp[0] = 1;
        for(int i = 1; i < MAXL; i++)
            xp[i] = xp[i - 1] * x;
    }
    void cal(DATA *s, int l, ULL *f){
        f[l] = 0;
        for(int i = l - 1; i >= 0; i--)
            f[i] = f[i + 1] * x + s[i];
    }
    ULL get(int i, int l, ULL *f){
        return f[i] - f[i + l] * xp[l];
    }
};