

字符串哈希

Hash 的思想¶

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

Warning

这里的“值域较小”在不同情况下意义不同。

在哈希表中，值域需要小到能够接受线性的空间与时间复杂度。

在字符串哈希中，值域需要小到能够快速比较（、都是可以快速比较的）。

同时，为了降低哈希冲突率，值域也不能太小。

我们定义一个把字符串映射到整数的函数，这个称为是 Hash 函数。

我们希望这个函数可以方便地帮我们判断两个字符串是否相等。

具体来说，哈希函数最重要的性质可以概括为下面两条：

在 Hash 函数值不一样的时候，两个字符串一定不一样；
在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

我们需要关注的是什么？

时间复杂度和 Hash 的准确率。

通常我们采用的是多项式 Hash 的方法，对于一个长度为的字符串来说，我们可以这样定义多项式 Hash 函数：。例如，对于字符串，其哈希函数值为。

特别要说明的是，也有很多人使用的是另一种 Hash 函数的定义，即，这种定义下，同样的字符串的哈希值就变为了了。显然，上面这两种哈希函数的定义函数都是可行的，但二者在之后会讲到的计算子串哈希值时所用的计算式是不同的，因此千万注意 不要弄混了这两种不同的 Hash 方式 。由于前者的 Hash 定义计算更简便、使用人数更多、且可以类比为一个进制数来帮助理解，所以本文下面所将要讨论的都是使用来定义的 Hash 函数。

这里面的和需要选取得足够合适才行，以使得 Hash 函数的值分布尽量均匀。

如果和互质，在输入随机的情况下，这个 Hash 函数在上每个值概率相等，此时单次比较的错误率为。所以，哈希的模数一般会选用大质数。

Hash 的实现¶

参考代码：（效率低下的版本，实际使用时一般不会这么写）

using std::string;

const int M = 1e9 + 7;
const int B = 233;

typedef long long ll;

int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = (ll)(res * B + s[i]) % M;
  }
  return res;
}

bool cmp(const string& s, const string& t) {
  return get_hash(s) == get_hash(t);
}

Hash 的分析与改进¶

错误率¶

若进行次比较，每次错误率，那么总错误率是。在随机数据下，若 , ，错误率约为，并不是能够完全忽略不计的。

所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。

多次询问子串哈希¶

单次计算一个字符串的哈希值复杂度是，其中为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。

一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个进制的数对取模的结果，这样的话每次就能快速求出子串的哈希了：

令表示，即原串长度为的前缀的哈希值，那么按照定义有

现在，我们想要用类似前缀和的方式快速求出，按照定义有字符串的哈希值为

对比观察上述两个式子，我们发现成立（可以手动代入验证一下），因此我们用这个式子就可以快速得到子串的哈希值。其中可以的预处理出来然后的回答每次询问（当然也可以快速幂的回答每次询问）。

Hash 的应用¶

字符串匹配¶

求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可。

最长回文子串¶

二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度。

这个问题可以使用 manacher 算法在的时间内解决。

确定字符串中不同子字符串的数量¶

问题：给定长为的字符串，仅由小写英文字母组成，查找该字符串中不同子串的数量。

为了解决这个问题，我们遍历了所有长度为的子串。对于每个长度为，我们将其 Hash 值乘以相同的的幂次方，并存入一个数组中。数组中不同元素的数量等于字符串中长度不同的子串的数量，并此数字将添加到最终答案中。

为了方便起见，我们将使用作为 Hash 的前缀字符，并定义。

参考代码

int count_unique_substrings(string const& s) {
  int n = s.size();

  const int b = 31;
  const int m = 1e9 + 9;
  vector<long long> b_pow(n);
  b_pow[0] = 1;
  for (int i = 1; i < n; i++) b_pow[i] = (b_pow[i - 1] * b) % m;

  vector<long long> h(n + 1, 0);
  for (int i = 0; i < n; i++)
    h[i + 1] = (h[i] + (s[i] - 'a' + 1) * b_pow[i]) % m;

  int cnt = 0;
  for (int l = 1; l <= n; l++) {
    set<long long> hs;
    for (int i = 0; i <= n - l; i++) {
      long long cur_h = (h[i + l] + m - h[i]) % m;
      cur_h = (cur_h * b_pow[n - i - 1]) % m;
      hs.insert(cur_h);
    }
    cnt += hs.size();
  }
  return cnt;
}

例题¶

CF1200E Compress Words

给你若干个字符串，答案串初始为空。第步将第个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第个串的前缀的字符串），求最后得到的字符串。

字符串个数不超过，总长不超过。

题解

每次需要求最长的、是原答案串的后缀、也是第个串的前缀的字符串。枚举这个串的长度，哈希比较即可。

当然，这道题也可以使用 KMP 算法解决。