BKDRHash 哈希函数

字符串哈希函数

哈希函数擅长于解决这一类问题：在很多字符串中，尽快操作某个字符串，如查询、修改等，它能以最快的速率完成对字符串的访问。

用哈希函数对每个字串进行哈希，分别映射到不同的数字，即一个整数哈希值，然后根据哈希值找到字串。

该算法的核心是找到哈希函数。理论上来说任何函数 $h(x)$ 都可以是哈希函数，不过一个好的哈希函数应该避免冲突——被称为完美哈希函数，指的是没有冲突的哈希函数：把 $n$ 个字串的 $key$ 值映射到 $m$ 个整数上，如果对任意的 $key1$ $\neq$ $key2$，都有 $h(key1) \neq h(key2)$，那么这就是一个完美哈希函数。

值得注意的是，这里的 $m$ 并不指代“这 $n$ 个字串映射出来的结果”，应该理解为“准备了 $m$ 个整数用以映射，防止出现数据丢失”。

此时，必然有 $n \leq m$，特别地，如果 $n = m$，称为最小完美哈希函数。

通俗地说，就是要找到一种函数关系，使得每一个字串的 $key$ 值都能唯一确定地映射到某个整数上，且这个整数的范围越小越好。否则就会占用很大一部分空间。

哈希函数有很多种，其中最好的是 BKDRHash 函数，其好处是几乎不会发生冲突。

然而，通常我们得到的映射值都会很大，为了保证空间利用率，我们可以通过取模的方式进行。也就是“溢出空间”的部分再从头开始索引，但这样有可能出现冲突，需要小心地设计。

一个别出心裁的优化是：我们无需使用低效的取模运算，我们可以取空间大小为 $M = 2^{64}$，其中 $64$ 是 unsigned long long 型的长度，那么对于一个 unsigned long long 型的哈希值 $H$ 来说，当 $H > M$ 时会自动溢出，等价于自动对 $M$ 取余。

BKDRHash

介绍完哈希函数的原理之后，接下来介绍 BKDRHash，它是一种进制哈希。

设定一个进制 $P$，需要计算一个字符串的哈希值时，把每个字符看作每个进制位上的一个数字，这个串转化成一个基于进制 $P$ 的数，最后对 $M$ 取余数，就得到了这个字符串的哈希值。

例如，计算一个只有小写字母的字符串的哈希值，以”abc”为例，令进制 $P=131$，有以下两种方法。

• 把每个字符看作一个数字，即 $a=1,b=2,…,z=26$，然后把字符串的每位按进制 $P$ 的权值相加，即 $1 \times 131^2 + 2 \times 131^1 + 3 \times 131^0 = 17426$。
• 也可以直接把每个字符对应的 ASCII 码作为计算时使用的数字，计算方法与上面一致，即 $a=97,b=98,……$，求解得到 $1677554$

进制 $P$ 常用的值有 $31,131,1313,13131,131313$ 等，用这些值可以有效防止碰撞。

模板代码

下面将用P3370 【模板】字符串哈希演示进制哈希的模板书写流程。

#include <iostream>
#include <algorithm>
#define ull unsigned long long

using namespace std;

const int maxN = 10010;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n;

string s;

ull a[maxN];

// 哈希函数
ull BKDRHash(string s)
{
    ull P = 131, H = 0; // P 表示进制，H 表示哈希值
    int n = s.size();
    for (int i = 0; i < n; i++)
        H = H * P + s[i] - 'a' + 1;
    return H;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        a[i] = BKDRHash(s);
    }
    int ans = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        if (a[i] != a[i + 1])
            ans++;
    printf("%d\n", ans);
}

进制哈希的应用

由于进制哈希把字符串的每位看作一个数字，所以字符串的各种操作对应的哈希计算都能按 $P$ 进制数的计算规则进行。

设字符串 $S$ 的哈希值为 $H(S)$，长度为 $len(s)$。对于字符串 $S_1$ 和 $S_2$ 的组合，即 $S_1 + S_2$，可以认为是字符串 $S_1$ 向左移动了 $len(S_2)$ 位，其哈希值为 $H(S_1) \times P^{len(S_2)} + H(S_2)$。

利用这个性质，我们可以快速计算字符串 $S$ 的所有前缀。例如字符串”abcdefg”，其前缀就有”a”，”ab”，”abc”……

显然地，计算出 $H(a)$ 后，$H(ab) = H(a) \times P + H(b)$，$H(abc) = H(ab) \times P + H(c)$，等等。只要提前计算出每一位的哈希值，那么所有前缀的哈希值都只要在一次循环中得到。而这个计算是 $O(1)$ 的。

计算得到前缀之后，我们就可以利用前缀和的思想，迅速求出每一个子串的哈希值。例如，$H(de) = H(abcde) – H(abc) \times P^2$，只需要预先处理好 $P$ 的幂值。同样，仿照前缀和的代码，我们可以写出求解区间 $[L,R]$ 的哈希值的代码（其中 P[i] 代表 $P$ 的 $i$ 次方）

ull get_hash(ull L, ull R)
{
    return H[R] - H[L-1] * P[R-L+1];
}

尽管进制哈希在求解部分问题时并不是最优解，但作为一个“通用解”和“基础解”仍然具有很大的意义。下面给出两个类型题。

进制哈希与最长回文集

查找一个长度为 $n$ 的字符串 $S$ 中的最长回文串

这种题目的标准做法是 Manacher 算法，复杂度为 $O(n)$。

而如果使用进制哈希，其复杂度为 $O(n \log_2 n)$，尽管效率上不如 Manacher，但编码较为简单。

如何利用前缀找到回文串？显然，回文串是正着读、反着读都相等的字符串，也就是字符对称，也就是说它们的哈希值应该也是相等的。

不过，如果从头到尾遍历 $S$ 的所有子区间，需 $O(n^2)$ 次。我们可以使用“中心扩展法”进行优化：以 $S$ 的每个字符为中心，左右扩展，如果左右对应的字符是相同的，就是一个回文串。不过，这样的做法仍然需要 $O(n)$ 的时间。

考虑二分加速：扩展中心字符的左右求回文串的长度具有单调性，可以用二分法加速。优化后的时间复杂度为 $O(\log_2 n)$，再加上计算哈希值的部分，可以认为最终的时间复杂度为 $O(n \log_2 n)$。

给出例题：P3501 [POI2010] ANT-Antisymmetry

#include <iostream>
#include <algorithm>
#define ll long long
#define ull unsigned long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 5e5 + 5;
const int pp = 131;

int n;
ll ans;

ull p[maxN], f[maxN], g[maxN];

char s[maxN], t[maxN];

// 二分，mid 是半径
void bin_search(int x)
{
    int L = 0, R = min(x, n - x);
    while (L < R)
    {
        int mid = (L + R + 1) >> 1;
        if ((ull)(f[x] - f[x - mid] * p[mid]) == (ull)(g[x + 1] - g[x + 1 + mid] * p[mid]))
            L = mid;
        else
            R = mid - 1;
    }
    ans += L;
}

int main()
{
    n = read();
    scanf("%s", s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++)
        s[i] == '1' ? t[i] = '0' : t[i] = '1';
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] * pp;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] * pp + s[i];
    for (int i = n; i >= 1; i--)
        g[i] = g[i + 1] * pp + t[i];
    for (int i = 1; i < n; i++)
        bin_search(i);
    printf("%lld\n", ans);
    return 0;
}

进制哈希与循环节

下面例题的标准解法是 KMP 算法，复杂度为 $O(n)$。如果用哈希进制求解，略差一点，但也非常接近 $O(n)$。

P4391 [BOI2009] Radio Transmission 无线传输

思路非常暴力：枚举这个循环节的长度，然后判断之后的每一个长度相同的区间是否和循环节相同，如果有多出来的段落，就单独计算。

#include <iostream>
#define ull unsigned long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 1e6 + 5;
const int PP = 131;

char s[maxN];
ull P[maxN], a[maxN], N;

ull get_hash(int L, int R)
{
    return a[R] - a[L - 1] * P[R - L + 1];
}

int main()
{
    N = read();
    scanf("%s", s + 1);
    P[0] = 1;
    for (int i = 1; i <= N; i++)
        P[i] = P[i - 1] * PP;
    for (int i = 1; i <= N; i++)
        a[i] = a[i - 1] * PP + s[i];
    for (int i = 1; i <= N; i++)
    {
        bool flag = true;
        ull last = get_hash(1, i);
        for (int j = 1; j * i + i <= N; j++)
            if (get_hash(j * i + 1, j * i + i) != last)
            {
                flag = false;
                break;
            }
        if (N % i != 0)
        {
            int len = N % i;
            if (get_hash(1, len) != get_hash(N - len + 1, N))
                flag = false;
        }
        if (flag)
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}