字符串哈希

字符串哈希

字符串哈希就是将一个字符串通过哈希函数映射成一个整数，那么判断两个字符串是否相同时就可以判断它们的哈希值是否相同。

字符串哈希是O(len)的预处理，O(1)的查询，len是字符串的长度。

容易想到的是哈希会出现冲突，即两个不同的字符串得到的哈希值相同，所以我们要尽量的避免这一种情况，最好我们的映射是一个单射。

字符串哈希最简单的的应用有：

• 给出n个字符串，判断有多少个字符串不相同
• 给出一个模式串和一个待匹配串，判断模式串是否在待匹配串中出现及记录出现的位置

对于第一个应用，就是统计不同的哈希值

对于第二个应用，分别计算出模式串和待匹配串的哈希值，for一下待匹配串，看看长度为|模式串|的子串的哈希值是否与模式串相同即可

单Hash

假设我们的字符串都由小写字母构成，我们规定idx(s[i])为s[i]-‘a’+1（当然也可以直接用s[i]的ASCII值）

哈希公式为：hash[i] = (hash[i-1]*p + idx(s[i])) % mod

其中p和mod都为大质数

比如取p=13, mod=101, 我们对abc进行Hash

hash[0] = 1

hash[1] = (hash[0]*13 + 2) % 101 = 15

hash[2] = (hash[1]*13 + 3) % 101 = 97

所以97就是abc的哈希值

自然溢出Hash

我们利用unsigned long long类型的特性，其实就是ull类型溢出之后会自动对2^64-1取膜，来进行Hash

与单哈希的公式没什么不同的，只是省略了mod

双Hash

双Hash相对比较安全，可以较好的避免冲突

其实就是用两个Hash函数对同一个字符串进行Hash，一个字符串对应两个Hash值

Hash函数为：

hash1[i] = (hash1[i-1]*p + idx(s[i])) % mod1

hash2[i] = (hash2[i-1]*p + idx(s[i])) % mod2

两个不同的模数取大质数即可，用pair<hash1[i], hash2[i]>来表示si的Hash值

获取子串的哈希值

假设我们有一个长度为5的字符串，用si表示第i个字符，根据上面的Hash定义，我们可以得到下面的式子：

hash[1] = s1

hash[2] = s1 * p + s2

hash[3] = s1 * p^2 + s2 * p + s3

hash[4] = s1 * p^3 + s2 * p^2 + s3 * p + s4

hash[5] = s1 * p^4 + s2 * p^3 + s3 * p^2 + s4 * p + s5

假如我们要得到s3s4这一个子串的哈希值，根据定义这个值为s3 * p + s4

根据上面的式子观察，hash[4] - hash[2]就可以消除掉s1和s2的影响，但是因为p的指数不对，我们还得将hash[2]乘以p^(4-3+1)

我们可以归纳出以下的公式：

s[l, r]的哈希值 = hash[r] - hash[l-1]*p^(r-l+1)

但是我们还有一个mod，所以公式如下：

hash = (hash[r] - hash[l-1]*p^(r-l+1)) % mod

这个式子看起来没什么问题，但是涉及到取膜我们还是得小心一点点，注意到括号里面的是减法，那么就有可能是负数，所以我们将式子变换成下面的样子：

hash = ((hash[r] - hash[l-1]*p^(r-l+1))%mod + mod)%mod

如果需要多次计算子串的哈希值，可以预处理p的n次方

例题

用一个最最最简单的例题来演示一下吧

洛谷p3370

就是计算不同的字符串数量

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
typedef pair<int, int> P;
const int maxn = 3e5+5;
const ll mod = 1e9+7;
using namespace std;

ull a[10005];
ull gethash(string s)
{
	ull ans = 0, base = 131;
	int len = s.length();
	for(int i=0;i<len;i++)
		ans = ans*base+s[i];
	return ans;
}
int main()
{
	IO;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		a[i] = gethash(s);
	}
	sort(a+1, a+n+1);
	set<ull> s;
	for(int i=1;i<=n;i++)
		s.insert(a[i]);
	cout<<s.size()<<"\n";
	return 0;
}