什么是字符串哈希

字符串Hash可以通俗的理解为，把一个字符串转换为一个整数。

如果我们通过某种方法，将字符串转换为一个整数，就可以便的确定某个字符串是否重复出现过，这是最简单的字符串Hash应用情景了。

当然也不难想到，如果有不同的两个字符串同时Hash到一个整数，这样就比较麻烦了。我们希望这个映射是一个单射，所以问题就是如何构造这个Hash函数，使得他们成为一个单射。

Hash方法

给定字符串 s，则 asc[s[i]] = s[i] - ‘a’ + 1.

自然溢出方法

1 2	unsigned long long Hash[n]; Hash[i] = Hash[i - 1] * p + asc[s[i]]

利用unsigned long long的范围自然溢出，相当于自动对 2^64 -1 取模。

单哈希方法

1	Hash[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD

其中 p 和 MOD 均为质数，且有 p < MOD。

对于此种Hash方法，将 p 和 MOD 尽量取大即可，这种情况下，冲突的概率是很低的。

如取 p = 13, MOD = 101, 对字符串 “abc” 进行Hash。这里注意asc[s[i]]是s[i]的ascii码加1.

Hash[0] = 1;

Hash[1] = (Hash[0] * 13 + 2) % 101 = 15; // s[i] = ‘b’, asc[s[i]] = ‘b’ - ‘a’ + 1 = 2

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

结果是Hash[n]，即Hash[2]。所以此时认为 97 就是字符串”abc”的值。

双哈希方法

将一个字符串用不同的MOD Hash两次，将这两个结果用一个二元组表示，作为Hash结果。

1 2	Hash1[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD1; Hash2[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD2;

Hash的结果为 < Hash1[n], Hash2[n] >。

这种Hash很安全。

求子串公式

假设有一个∣S∣=5 的字符串，设 Si 为第 i 个字符，其中 1 ≤ i ≤ 5。

根据定义分别求出hash[i]：

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 的hash值，不难得出为s3 ∗ p + s4。
Hash[4] - Hash[2] * pow(p, 4 - 3 + 1)

所以公式如下：

Hash[l~r] = Hash[r] - Hash[l - 1] * pow(p, r - l + 1)

考虑到取模：

Hash[l~r] = ((Hash[r] - Hash[l - 1] * pow(p, r - l + 1)) % MOD + MOD) % MOD

应用

POJ2774

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define maxn 100010
#define p 131
// #define INF 0x3f3f3f3f
// #define MOD 1000000007

// Hash1和Hash2存储两个字符串的哈希值，
// po记录p的乘方(相当于转化为p进制)，tmp用于比较(后面会讲解)
ull Hash1[maxn], Hash2[maxn], po[maxn], tmp[maxn];
int len1, len2;  // 两字符串的长度
char s1[maxn], s2[maxn];

// 求h的子串s[l~r](包括s[l]和s[r])的Hash值
ull getHash(ull* h, int l, int r) {
	return h[r] - h[l - 1] * po[r - l + 1];
}

/*
check函数用来判断是否有长度为len的相同子串
先将Hash1的长度为len的子串的Hash值依次求出，存入tmp数组中
将tmp由小到大排序(这里排序只是为了便于Hash2的二分查找)
因为二分查找要求数组有序！
 */
bool check(int len) {
	int cnt = 0;
	for(int i = 1; i + len - 1 <= len1; i++)
		tmp[cnt ++] = getHash(Hash1, i, i + len - 1);
	sort(tmp, tmp + cnt);
	for(int i = 1; i + len - 1 <= len2; i++) {
		ull x = getHash(Hash2, i, i + len - 1);
		if(binary_search(tmp, tmp + cnt, x)) return true;
		// 这里用到了<algorithm>中的binary_search函数，这是一个bool类型函数，
		// 是在[tmp, tmp + cnt)，即[tmp, tmp + cnt - 1]范围内
		// 二分查找x，如果找到了就返回true，否则返回false
	}
	return false;
}

void init_po() {  // 将p的乘方都算出来，打表
	po[0] = 1;
	for(int i = 1; i < maxn; i++)
		po[i] = po[i - 1] * p;
}

int main() {
	init_po();
	while(~scanf("%s%s", s1 + 1, s2 + 1)) {  // s1和s2都从索引1开始存储
		len1 = strlen(s1 + 1);
		len2 = strlen(s2 + 1);

		// 计算s1和s2的Hash值
		Hash1[0] = Hash2[0] = 0;
		for(int i = 1; i <= len1; i++)
			Hash1[i] = Hash1[i - 1] * p + (s1[i] - 'a');
		for(int i = 1; i <= len2; i++)
			Hash2[i] = Hash2[i - 1] * p + (s2[i] - 'a');

		// 二分查找最大长度
		int l = 0, r = min(len1, len2);
		int ans = 0;
		while(l <= r) {
			int m = (l + r) >> 1;  // 移位更快
			if(check(m)) {  // 如果m满足长度为m的子串相等
				l = m + 1;  // 就增大左边界l，看看有没有更大的长度
				ans = m;    // ans更新为当前的最大值
			}
			else
				r = m - 1;  // 没有找到，那就先减小右边界看看有没有符合的m
		}
		printf("%d\n", ans);
	}
	return 0;
}