字符串Hash学习笔记

• 哈希算法

  哈希算法是通过一个哈希函数 $H$，将一种数据（包括字符串、较大的数等）转化为能够用变量表示或是直接就可作为数组下标的数。

• 哈希值

  通过哈希函数转化的得到的数值。可以通过哈希值实现快速查找和匹配。

简介

寻找长度为 $n$ 的主串 $S$ 中的匹配串 $T$（长度为 $m$）出现的位置或次数的问题属于字符串匹配问题。

朴素的想法是枚举所有起始位置，再直接检查是否匹配。

可以不使用 $O(m)$ 的直接比较字符串的方法，而是比较长度为 $m$ 的主串 $S$ 的子串的哈希值是否相等，这就是哈希算法的原理——字符串 Hash。

流程

所以我们需要用到一个叫做滚动哈希的优化技巧。

我们选取两个合适的互质常数 $b$ 和 $h$（$b<h$），假设字符串 $C=c_1{c}_2\cdots c_m$，那么我们定义哈希函数：$H(C)=(c_1{b}^{m-1}+c_2{b}^{m-2}+\cdots +c_m{b}^0)\mathrm{mod}h$。

正常的数字是十进制的，这里 $b$ 是基数，相当于把字符串看作是 $b$ 进制数。

这一过程是递推计算的。下面讲解省略求模运算，因为可以用自然溢出大法！！！
$$H(C,k+1)=H(C,k)\times b+c_{k+1}$$
举个栗子：

字符串 $C=\text{ACDA}$，令 $1$ 表示 $\text{A}$，$2$ 表示 $\text{B}$，以此类推。
H ( C , 1 ) = 1 H ( C , 2 ) = 1 × b + 3 H ( C , 3 ) = 1 × b 2 + 3 × b + 4 H ( C , 4 ) = 1 × b 3 + 3 × b 2 + 4 × b + 1

​H(C,1)=1H(C,2)=1×b+3H(C,3)=1×b2+3×b+4H(C,4)=1×b3+3×b2+4×b+1​
判断字符串 $C=c_1{c}_2\cdots c_m$ 从位置 $k+1$ 开始的长度为 $n$ 的子串 $C^{\prime }=c_{k+1}{c}_{k+2}\cdots c_{k+n}$ 的哈希值与另一匹配串 $S=s_1{s}_2\cdots s_n$ 的哈希值是否相等。
$$H(C^{\prime })=H(C,k+n)-H(C,k)\times b^n$$

于是只需要预求得 $b^n$，就能在 $O(1)$ 时间内得到任意字符串的子串哈希值，从而完成字符串匹配。于是乎，字符串匹配问题的算法时间复杂度就为 $O(n+m)$。

举个栗子：

字符串 $C=\text{ACDA}$，$S=\text{CD}$，$k=1$，$n=2$。
H ( C ′ ) = H ( C , 1 + 2 ) − H ( C , 1 ) × b 2 = ( 1 × b 2 + 3 × b + 4 ) − ( 1 × b 2 ) = 3 × b + 4 H ( S ) = 3 × b + 4

H(C′)H(S)​=H(C,1+2)−H(C,1)×b2=(1×b2+3×b+4)−(1×b2)=3×b+4=3×b+4​

正确性

出现不同字符串哈希值相等的概率越低越好。

所以有以下两种方法：

• 自然溢出法

  利用 unsigned long long 无符号整数计算哈希值，相当于对哈希值 $\mathrm{mod}{2}^{64}$。

• 双模法

  顾名思义，就是搞一个二元数组存储哈希值，$\mathrm{mod}$ 两个数，两个数都相同哈希值才相同。

实现

Portal.

代码如下：

#include 
using namespace std;

typedef unsigned long long ull;
const int mmax=1505,maxn=10005;
ull base=131,prime=23317,mod=212370440130137957;
int N,a[maxn],ans=1;
char s[mmax];
ull hash[maxn],power[maxn];

ull hashh(char s[])
{
	int len=strlen(s);
	ull ans=0;
	for(int i=0;i<len;i++)
		ans=(ans*base+(ull)s[i])%mod+prime;
	return ans;
}

int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
		scanf("%s",s),a[i]=hashh(s);
	sort(a+1,a+N+1);
	for(int i=1;i<N;i++)
		if(a[i]!=a[i+1]) ans++;
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30