Hash——温暖人心的算法

简介
计算Hash
前缀Hash递推
快速计算子串Hash
用Hash匹配字符串
综合：P2852 [USACO06DEC]Milk Patterns G

简介

Hash，将一个字符串映射到一个数字上。

计算Hash

计算Hash的方法有很多种，比如说在密码学中常用的 \(\texttt{MD5}\) 和 \(\texttt{SHA256}\) 等。

但是我们一般使用一个简单的方法：

将字符串看成一个 \(B\) 进制数。（\(B \ge \textbf{字符集大小}\)）
将这个 \(B\) 进制数对 \(p\) 取模，要求 \(B,p\) 互质。

显然，如果有 \(p+1\) 个互不相同的字符串，那么一定有至少一对 \(\operatorname{Hash}\) 相等的字符串。

所以，\(p\) 一般都很大，如 \(2^{64},2^{63},10^{9}+7\) 等。

注：大多数情况下，\(10^{9}+7\) 仍然不够用，因为当有 \(\sqrt{p}\) 个字符串时，\(\operatorname{Hash}\) 相同（我们称之为Hash冲突）的概率就很高了。

Tip：在C++中，如果用 unsigned long long 来保存，那么可以考虑自然溢出，这样其实自带 \(p=2^{64}\)。

其实 \(p\) 最好为质数，但是一般不需要。

后文中，用 \(\operatorname{hash}(x)\) 表示字符串 \(x\) 的Hash值。

前缀Hash递推

预处理字符串 \(s\) 的所有前缀子串 \(s[1:i]\) 的Hash \(H[i]\)，\(H\) 就是 \(s\) 的前缀Hash，后缀Hash同理。

那么有一个显然的递推公式：

\[H[i]=H[i-1]\times B+\operatorname{ToInteger}(s[i]) \pmod{p}
\]

前缀Hash可以处理以下问题：

给出几个字符串，求一个模式串 \(s\) 是多少个字符串的前缀。

将所有字符串的前缀Hash求出来，合并成一个有序数组（或者 std::set），然后求出 \(\operatorname{hash}(s)\)，将 \(\operatorname{hash}(s)\) 在那个数组/set上二分。

快速计算子串Hash

先使用上面章节的方法递推出前缀Hash \(H\)。

那么子串 \(s[l:r]\) 的Hash计算公式为：

\[\operatorname{hash}(s[l:r])=H[r]-H[l-1]\times B^{r-l+1} \pmod{p}
\]

就可以在 \(O(\log n)\)（如果使用光速幂就是 \(O(1)\)）求字符串中的任意连续字串的hash了。

用Hash匹配字符串

如果 \(\operatorname{hash}(x)=\operatorname{hash}(y)\)，那么 \(x=y\)。

由于hash冲突的存在，可能并不准确，但是只要 \(p\) 尽可能的大就行。

综合：P2852 [USACO06DEC]Milk Patterns G

给出一个长度为 \(n\) 数列 \(A\)，问出现次数为 \(K\) 的字串长度最大是多少？

\(1 \le K \le n \le 20000,1 \le A_i \le 1000000\)

第一道没看题解A掉的紫题

正解SAM，但是可以用Hash水过。

预处理前缀Hash，二分字串长度 \(L\)，对于每一个长度为 \(L\) 的子串计算Hash，用 std::unordered_map 统计一下就好。

时间复杂度 \(O(n\log^{2} n)\)。

代码：（写到一半二分不会写，还要请教@exited，雾）

#include <bits/stdc++.h>

#define DEBUGGING 1

#define debug(...) if(DEBUGGING){printf(__VA_ARGS__);putchar('\n');}

using namespace std;

int n,k;

int a[20005];

int l,r;

int mid;

unsigned long long qzhash[20005];

const int base =1000001;

const unsigned long long mod = 2e63;

#define int unsigned long long

int pow(int a,int b,int mod) {

#define MAG (1ull)

	int ans=1;

	for(; b; b>>=1,a=MAG*a*a%mod) {

		if(b&1) {

			ans=MAG*ans*a%mod;

		}

	}

#undef MAG

	return ans;

}

#undef int

unsigned long long any_hash(int l,int r){

	return (qzhash[r]-(qzhash[l-1]*pow(base,r-l+1,mod))%mod)%mod;

}

unordered_map<unsigned long long,int> mmap;

int max_mm = 0;

bool check(int length){

	max_mm=0;

	mmap.clear();

	for(int l=1,r=length;l<=n&&r<=n;l++,r++){

		unsigned long long current_hash=any_hash(l,r);

		mmap[current_hash]++;

		max_mm = max(max_mm, mmap[current_hash]);

	}

	return max_mm >= k;

}

int ans=0;

int main(){

	cin>>n>>k;

	for(int i=1;i<=n;i++){

		cin>>a[i];

	}

	for(int i=1;i<=n;i++){

		qzhash[i]=qzhash[i-1]*base%mod;

		qzhash[i]+=a[i];

		qzhash[i]%=mod;

	}

	l=1,r=n;

	while(l<r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			ans=mid;

		}

		else{

			r=mid;

		}

	}

	cout<<ans;

	return 0;

}

巴特西