【字符串】Hash

字符串哈希简介，当初按教学稿写的，应该还比较详细

简介

引入：给定$m$​​ 个字符串，求不同的字符串有多少个？

暴力法：每次匹配两个字符串，假设字符串平均长度为$n$​ ，则最坏情况时间复杂度$O(nm^2)$​​​​​​​，复杂度过高。

考虑如何优化，注意到中间出现了重复匹配，如果有相同的两个字符串，它们分别与其他字符串比较了一遍。如果相同的某字符串有一个标记a，与它不同的字符串有标记b,c,d…，那么就可以统计标记的个数来解决问题。

标记的含义：相同字符串拥有同一种标记，不同字符串标记不同——考虑映射到正整数，对每个字符串进行映射，通过排序比较有多少相同的映射值，比较部分复杂度$O(m\log m)$​ 。

字符串哈希本质是一种映射，方法很多。

map/unordered_map

• 红黑树/哈希表，$O(\log n)$/接近$O(1)$，有序/无序

进制法哈希

原理概述

• 字符集中的每个字符对应$Base$​​​ 进制下的一个数（不能为0，why？），则每一个字符串都可看作一个$Base$​​​​​​​​ 进制数，这样的方法得到的数值就是这个字符的哈希值，通过比较每个字符串的哈希值即可判断字符串是否相同
• 实际应用中，要对上述哈希值通过取模将其限定在一定的范围（比如int），方便比较。
• 一般将哈希函数记为：

$f(S)=\Sigma_{i=0}^{n-1}S[i]\times Base^i (\mod M)$

• 其中$S$​ 首位从$0$​ 开始编号。这里也有另一种记法$f(S)=\Sigma_{i=0}^{n-1}S[i]\times Base^{n-i-1} (\mod M)$​​，是一个道理，不过最高次的位置不同。我们采用第一种记法。

//一般不这么写，但是原理是这样
int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = (long long)(res * Base + s[i]) % mod;
  }
  return res;
}

模数选择

尽量选择素数，注意，如果选择一个$10^9$ 级别的数，随机$\sqrt{10^9}$​​ 个串就有大概率出现至少一对哈希值相等的不同串（生日悖论）。常用模数有：$19260817$ ，$212370440130137957$ （$10^{18}$ 级别）。

哈希冲突

出现哈希值相等的不同串，这时便发生了哈希冲突，哈希值相同的不同字符串会被错判为相同字符串。冲突概率网上有严格推导。

解决：

• 双哈希：选择两个模数，对同一个字符串进行两次哈希求值，只有两个哈希值都相同的两个字符串才判定为相同。但是常数较大。
• 模数选择：对于算法竞赛的规模，一般一个$10^{18}$​​ 级别的大质数（如何找？Miller-Rabin算法，或是直接记住），基本没有问题。另一种选择是使用unsigned long long ，溢出时会自动对$2^{64}$ 取模。

Rabin-Karp实现

推导

引入：上述哈希有什么问题？单次计算一个字符串的哈希值复杂度$O(n)$​​​ ，如果多次询问一个字符串子串的哈希值，每次都需要重复计算。能不能让子串的哈希值由原字符串直接得到？

将上述进制数$Base$ 简记为$x$ ，记哈希函数为$f$ ，则哈希函数展开即为：

$f(S)=S[0] + S[1]x + \dots + S[n-2]x^{n-2} + S[n-1]x^{n-1}$

字符串$S$ 的从$i$ 开头的后缀记为$Suffix(S,i)$，记函数$H$ ：

$\begin{aligned} H(n)&=0\\ H(n-1)&=f(Suffix(S,n-1))=S[n-1] \\ H(n-2)&=f(Suffix(S,n-2))=S[n-2]+S[n-1]x \\ H(n-3)&=f(Suffix(S,n-3))=S[n-3]+S[n-2]x+S[n-1]x^2 \\ \vdots \\ H(1)&=f(Suffix(S,1))=S[1]+S[2]x+\dots+S[n-1]x^{n-2}\\ H(0)&=f(S)=S[0]+S[1]x+S[2]x^2+\dots+S[n-1]x^{n-1} \end{aligned}$

易得递推式：

$H(i)=H(i+1)x+S[i],0\leq i<n\\ H(n)=0$

我们可以$O(n)$ 求出一个字符串的$H$ ，利用$H$ 可以$O(1)$ 求出该字符串任意子串的哈希值：

$f(S[i..i+L])=S[i]+S[i+1]x+\dots+S[i+L]x^{L}=H(i)-H(i+L+1)x^{L+1}$

方法

在以上推导的基础上，总结Rabin-Karp实现流程：

• $O(N)$​ 递推预处理$x^i, 0\leq x\leq N$​
• 对于每个字符串，$O(n)$​ 求出一个字符串所有的$H$​
• $O(1)$​​​​ 查询任意子串的哈希值。

代码实现

typedef unsigned long long ull;
const int x = 233;
ull XP[N]; //XP[i]记录x^i的值
void initXP() //预处理
{
    XP[0]=1;
    for(int i=1;i<N;i++)
        XP[i]=XP[i-1]*x;
}
template <size_t SZ> //模板初始化长度
struct HashLCP
{
    ull H[SZ];
    void init(const char* s, size_t n=0) //C风格字符串
    {
        if(!XP[0])
            initXP();
        if(!n) 
            n=strlen(s);
        H[0]=0;
        for(int i=n-1;i>=0;i--)
            H[i]=s[i]-'a'+1+H[i+1]*x;
    }
    void init(const string s) //string
    {
        init(s.c_str(),s.length());
    }
    inline ull hash(int i,int j) //返回子串哈希值
    {
        return H[i]-H[j+1]*XP[j-i+1];
    }
    inline ull hash() //返回整个字符串的哈希值
    {
        return H[0];
    }
};
HashLCP <N> hs;

其他

注意：上面有提到哈希函数有两种写法，这里介绍的是后缀形式的，前缀形式同理，掌握一种即可。

周期串的性质：$[0,len-i-1)$ 和$[i,len-1)$ 相同