字符串哈希（BKDR_hash）

发表于 更新于 分类于 本文字数： 316 阅读时长 ≈ 1 分钟

参考字符串哈希中多项式 $Hash $函数定义：

$f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$
及其推论:

$f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}$

我们可以写出$Hash$的实现：

1
2
3
4
5
6
7
const LL M = 33951943;
const LL BA = 233;
    hash_at[1] = (sum[1] - sum[0]) % 3;
    for (int k = 2; k <= sum_0; k++)
    {
        hash_at[k] = ((sum[k] - sum[k - 1]) % 3 + hash_at[k - 1] * BA) % M;
    }

其中 hash_at[] 储存hash值
而又由推论，我们可以简易地借助快速幂来得到$[l,r]$的hash值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LL quikpower(LL b)
{
    LL ans = 1, base = BA;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
            ans %= M;
        }
        base *= base;
        base %= M;
        b >>= 1;
    }
    return ans;
}
LL gethash(int l, int r)
{
    if (l == 1)
        return hash_at[r];
    return (hash_at[r] + M - hash_at[l- 1]] * quikpower(r- l+ 1) % M) % M;
    //加M防止hash值为负数
}

由于unsigned long long的特性，我们有自然溢出的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define LL long long
const LL B = 13331;
typedef unsigned long long ull;
ull hashs[200087], po[200087];/*hashs储存hash值，po数组储存B的n次方*/
void hash_init()
{
    int sum_0 = n - sum[n];
    po[0] = 1;
    po[1] = B;
    hashs[bk[1]] = (sum[bk[1]] - sum[0]) % 3; 
    for (int k = 2; k <= sum_0; k++)
    {
        hashs[k] = ((sum[k] - sum[k - 1]) % 3 + hashs[k - 1] * B);
        po[k] = po[k - 1] * B;
    }
}
LL gethash(int l, int r)
{
    if (l == 1)
        return hashs[r];
    return (hashs[r] - hashs[l- 1] * po[r - l+ 1]);
}