映射

哈希算法广义来看是将一个难以表示的信息（比如字符串）和一个容易表示的信息（比如数字）建立一种映射关系。

这种映射通常不是普通的一一对应的映射（比如双射），因为这样映射的难度比较大。

比如，给定 $n$ 个字符串，如果将这 $n$ 个字符串标记为数字 $1\sim n$ ，那么再给出一个字符串，也不容易得到它对应的数字是多少，甚至不容易知道它是否已经映射过了。

所以哈希通常是牺牲了双射的严谨性，来保证映射容易实现。

即找一个容易实现的映射，构造一个大概率一对一，小概率多对一（从左到右映射一般不会一对多）的映射集合。

这样的想法称为哈希。

通常情况下，哈希的冲突（多对一）的概率很小。

但是要解决也有一些办法：

一种是用多种哈希方式，在每种哈希方式都一一映射的时候才成立

另一种是建立哈希表，每个映射后的值为表头，内存着多个原数值

字符串哈希

一般字符串哈希是一种将字符串映射成数字的方式，最常用的是进制法

即将整个字符串看作一个 $X$ 进制的数字，每个字符表示不同的数字，然后将这个字符串转化成十进制数

比如可以将 $a\sim z$ 表示成 $1\sim 26$，然后每个字符串都可以看作一个 $27$ 进制的数字了

（将 $a\sim z$ 视作 $0\sim 25$ 也可以，但是这样 $aa$ 和 $a$ 都是 $0$ ，会增大冲突概率）

设 $h[i]$ 是字符串 $s[1]\sim s[i]$ 的哈希值，那么尾巴每增加一个字符，就加上 $h[i+1]=h[i]\ast base+s[i+1]$。

其中 $base$ 是你规定的进制数。

然而这样数字通常会很大，存不下，好办法是给数字取模，这样就会导致有的不同数字取完模变成一样的数字。

没事，我们假装这种情况不存在，然后做完了（目移）

好吧，为了减小冲突的概率，要尽量大质数作为模数。

大是为了让值域尽可能大，减小冲突概率。

选用质数 $p$ 是因为，模数的任何因子 $d$ ，都会让值域退化到$\frac{p}{d}$。

比如选用了 $2p$ 那么如果映射到的数字都是 $2$ 的倍数，就只有 $0,2,4,\dots ,2p-2$。

而如果 $p$ 是质数，即使映射到的数字都是 $d$ 的倍数，也会遍历整个值域，值域不容易退化。

将字符串映射到数字后，就可以实现 $O(1)$ 比较等实现了

P3370 【模板】字符串哈希

查询哈希子串：

假设我们有整个字符串 $s$ 的哈希值 $hash(s[1\sim n])=\sum _{i=1}^{n}s[i]\ast bas{e}^{n-i}$

$s[l\sim r]$ 的哈希是 $\sum _{i=l}^{r}s[i]\ast bas{e}^{r-i}$

先截取 $s[1\sim r]$ 得到 $\sum _{i=1}^{r}s[i]\ast bas{e}^{r-i}$

多出的部分是 $(\sum _{i=1}^{l-1}s[i]\ast bas{e}^{l-1-i})\ast bas{e}^{r-l}$

所以 $s[l\sim r]$ 的哈希是 $\sum _{i=1}^{r}s[i]\ast bas{e}^{r-i}-(\sum _{i=1}^{l-1}s[i]\ast bas{e}^{l-1-i})\ast bas{e}^{r-l}$

令 $h[i]$ 是 $s[1\sim i]$ 的哈希，则

$h[l\sim r]=h[r]-h[l-1]\ast bas{e}^{r-l}$

拼接子串：

将字符串 $t$ 拼在 $s$ 后面

设字符串 $s$ 的长度为 $n$ ，$t$ 的长度为 $m$

$hash(st)=\sum _{i=1}^{n+m}st[i]\ast bas{e}^{n+m-i}$

$hash(s)=\sum _{i=1}^{n}s[i]\ast bas{e}^{n-i}$

$hash(t)=\sum _{i=1}^{m}t[i]\ast bas{e}^{m-i}$

则 $hash(st)=hash(s)\ast bas{e}^m+hash(t)$

有了拼接和拆分的方法，字符串哈希疑似就能上线段树了捏（事实上也能）

子串查询

应用

字符串匹配

基本应用，判断两个字符串的哈希值是否相同

判断回文

对字符串正着做一遍，反着做一遍，判断正反是否相同

最长公共前缀

先分别求两个字符串的哈希值

对前缀长度二分答案，然后用哈希判断

最长公共子串

先二分答案，将第一个串所有长度为二分值的子串的哈希值存在桶里

然后再枚举第二个串所有长度为二分值的答案，判断桶里是否存在。

练习题

1456：【例题2】图书管理

1457：Power Strings

1458：Seek the Name, Seek the Fame

1459：friends

1462：Antisymmetry

P2757 [国家集训队] 等差子序列 需要线段树