Hash学习小结

Hash

简要说明

  • (OI)中一般采用进制(hash).模数可以用(unsigned long long)自然溢出,也可以使用大质数.值得一提的是,(unsigned long long)的优点是好写,不用取模,缺点是可能会被良心出题人卡.如果为了万无一失,可以写双模数(hash),这个东西在绝大多数情况下可以保证正确性(参见Hash Killer III).
  • 关于进制(hash)两个最基础的东西:

(Hash[0]=0.Hash[i]=Hash[i]*Base+s[i] for i>0.)

(hash(l,r)=Hash[r]-Hash[l-1]*Base^{r-l+1}.)

  • 如果两个字符串按照如上算法得出的(hash)值相等,我们认为这两个字符串是相同的.
  • 下面是最近整理的关于(hash)的一些基础题.

题目

子串查找

  • 题意:给两个字符串(a,b),询问(b)在(a)的几个位置出现过.
  • 此题用(hash)做的话,只需求出字符串(b)的(hash)值,在字符串(a)中(O(n))枚举每个长度等于(|b|)的子串,判断(hash)值是否相等即可.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
typedef unsigned long long ull;
const ull Base=233;
ull Hash[MAXN],Pow[MAXN];
char a[MAXN],b[MAXN];
int n,m;
// Hash[i]=Hash[i-1]*Base+val[i].
inline ull calchash(int l,int len)//l to l+len-1
{
	return Hash[l+len-1]-Hash[l-1]*Pow[len];
}
int main()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	ull hashb=0;
	for(int i=1;i<=m;++i)
		hashb=hashb*Base+(ull)b[i];
	Pow[0]=1;
	for(int i=1;i<=n;++i)
		{
			Hash[i]=Hash[i-1]*Base+a[i];
			Pow[i]=Pow[i-1]*Base;
		}
	int ans=0;
	for(int i=1;i+m-1<=n;++i)
		if(calchash(i,m)==hashb)
			++ans;
	printf("%d
",ans);
	return 0;
}

图书管理

  • 题意:你需要维护一个字符串集合,支持插入字符串和询问一个字符串是否在其中.
  • 将每个字符串通过计算(hash)转化为整数,开一个桶记录是否出现过即可.
View code 

#include
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int Base=233;
const int P1=19260817,P2=999983;
bool Hashmap1[P1+10],Hashmap2[P2+10];
char buf[300];
int main()
{
	int n=read();
	while(n--)	
		{
			char op[5];
			scanf("%s",op);
			if(op[0]=='a')
				{
					scanf("%s",buf);
					int len=strlen(buf),hash1=0,hash2=0;
					for(int i=0;i

Power Strings

  • 题意:求一个字符串的最短循环节长度.
  • 暴力枚举循环节长度,对于每个可以整除总长度的循环节长度,依次算出每段的(hash)值,若全部相等,说明这是一个合法的循环节.
  • 这样枚举的时间复杂度为(O(ncdot lnn)),因为这是一个调和级数,函数(lnx)与它是共犯.
  • 此题还可用(fail(next))数组计算.最小循环节长度为(frac{n}{n-fail[n]}),若其为整数.否则为(|S|).
  • 后面还有一个相似的题,所以此题并没有代码.

Seek the Name, Seek the Fame

  • 题意:找出一个字符串中既是前缀又是后缀的子串的所有长度.
  • 此题使用(hash)十分简单,直接枚举每个前缀,与长度相等的后缀比较即可.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=4e5+10;
typedef unsigned long long ull;
const ull Base=233;
ull Hash[MAXN],Pow[MAXN+10];
int n;
char s[MAXN];
int ans[MAXN];
inline ull calchash(int l,int r)
{
	if(l==0)
		return Hash[r];
	return (Hash[r]-Hash[l-1]*Pow[r-l+1]);
}
int main()
{
	Pow[0]=1;
	for(int i=1;i<=MAXN;++i)
		Pow[i]=Pow[i-1]*Base;
	while(~scanf("%s",s))
		{
			n=strlen(s);
			Hash[0]=s[0];
			for(int i=1;i=1;--i)
				printf("%d ",ans[i]);
			puts("");
		}
	return 0;
}

三个朋友

  • 现在有一个字符串(U),是由(S)复制一次自身拼接后,再插入一个字符得到的.给出(U),若(S)唯一存在,求出(S),否则输出不存在或有多个.
  • 做法十分暴力.直接枚举是插入的哪一个字符.然后通过进制(hash)良好的运算能力求出两侧的(hash)值比较即可.注意细节的实现.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=2e6+10;
typedef unsigned long long ull;
const ull Base=233;
ull Hash[MAXN],Pow[MAXN+10];
int n;
char s[MAXN];
inline ull calchash(int l,int r)
{
	if(l>r)
		return 0;
	return (Hash[r]-Hash[l-1]*Pow[r-l+1]);
}
inline ull mergehash(ull hash1,ull hash2,int len)
{
	return hash1*Pow[len]+hash2;
}
int main()
{
	n=read();
	scanf("%s",s+1);
	if(n%2==0)
		{
			puts("NOT POSSIBLE");
			return 0;
		}
	Pow[0]=1;
	for(int i=1;i<=n;++i)
		Pow[i]=Pow[i-1]*Base;
	Hash[0]=0;
	for(int i=1;i<=n;++i)
		Hash[i]=Hash[i-1]*Base+s[i];
	int cnt=0,cutpos;
	ull res=0;
	for(int i=1;i<=n;++i)
		{
			ull hashpre,hashsuf;
			if(i<=n/2)
				hashpre=Hash[n/2+1]+(Hash[i-1]-Hash[i])*Pow[n/2-i+1];
			else
				hashpre=Hash[n/2];
			if(i<=n/2+1)
				hashsuf=Hash[n]-Hash[n/2+1]*Pow[n/2];
			else
				hashsuf=(Hash[i-1]-Hash[n/2]*Pow[i-n/2-1])*Pow[n-i]+Hash[n]-Hash[i]*Pow[n-i];
			if(hashpre==hashsuf)
				{
					++cnt;
					if(res && hashpre!=res)
						{
							puts("NOT UNIQUE");
							return 0;
						}
					res=hashpre;
					cutpos=i;
				}
		}
	if(!cnt)
		puts("NOT POSSIBLE");
	else
		{
			if(cutpos>n/2)
				{
					for(int i=1;i<=n/2;++i)
						printf("%c",s[i]);
				}
			else
				{
					for(int i=1;i<=n/2+1;++i)
						if(i!=cutpos)
							printf("%c",s[i]);
				}
			puts("");
		}
	return 0;
}

A Horrible Poem

  • 题意:给定一个字符串(S),询问若干次,每次询问(S)某个子串的最短循环节.
  • 此题和(Power Strings)类似,但要询问子串的答案多次.
  • 考虑(kmp)的做法,计算(fail)其实只需检验最长前后缀公共长度.
  • 用(hash)判断,每次枚举这个子串长度的质因数进行检验.若(d)不是循环节长度,显然(kd(kin mathbb{N_+}))也不可能是循环节长度.可以作为一个小优化.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=5e5+10;
typedef unsigned long long ull;
const ull Base=233;
ull Hash[MAXN],Pow[MAXN];
int ism[MAXN],prime[MAXN],cnt=0;
int mindiv[MAXN];
int n,q;
char s[MAXN];
void LinearShake()
{
	for(int i=2; i<=MAXN-10; ++i)
		{
			if(!ism[i])
				{
					prime[++cnt]=i;
					mindiv[i]=i;
				}
			for(int j=1; j<=cnt; ++j)
				{
					if(prime[j]*i>MAXN)
						break;
					ism[prime[j]*i]=1;
					mindiv[i*prime[j]]=prime[j];
					if(i%prime[j]==0)
						break;
				}
		}
}
inline ull calchash(int l,int r)
{
	return Hash[r]-Hash[l-1]*Pow[r-l+1];
}
inline int judge(int l,int r,int len)
{
	return (calchash(l,l+len-1)==calchash(r+1-len,r));
}
int main()
{
	n=read();
	scanf("%s",s+1);
	Pow[0]=1;
	Hash[0]=0;
	for(int i=1; i<=n; ++i)
		Hash[i]=Hash[i-1]*Base+s[i],Pow[i]=Pow[i-1]*Base;
	LinearShake();
	q=read();
	while(q--)
		{
			int l=read(),r=read();
			int val=r-l+1,cur=r-l+1;
			while(val!=1)
				{
					if(judge(l,r,r-l+1-cur/mindiv[val]))
						cur/=mindiv[val];
					val/=mindiv[val];
				}
			printf("%d
",cur);
		}
	return 0;
}

Beads

  • 题意:求一个串的最大循环节数目,这里规定最后一段不足循环节长度的段可以舍弃,并且段可以反转,即(123)和(321)被视作等价.

  • 显然只需要正着反着处理两个(hash)值,由于可以舍去最后一段,所以我们不使用计算(fail)的办法,而是(O(ncdot lnn))暴力枚举即可.

View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=2e5+10;
typedef unsigned long long ull;
const ull P=98754321,Base=2333;
map Hash;
ull prehash[MAXN],sufhash[MAXN];
ull Pow[MAXN];
int ans[MAXN],tp=0;
int res[MAXN];
int n,maxx=0;
int s[MAXN];
int main()
{
	n=read();
	Pow[0]=1;
	for(int i=1;i<=n;++i)
		{
			s[i]=read();
			Pow[i]=Pow[i-1]*Base%P;
			prehash[i]=(prehash[i-1]*Base+s[i])%P;
		}
	for(int i=n;i;--i)
		sufhash[i]=(sufhash[i+1]*Base+s[i])%P;
	for(int i=1;i*maxx<=n;++i)
		{
			Hash.clear();
			for(int j=1;j+i-1<=n;j+=i)
				{
					int l=j,r=j+i-1;
					ull pre=(prehash[r]-prehash[l-1]*Pow[r-l+1]%P+P)%P;
					ull suf=(sufhash[l]-sufhash[r+1]*Pow[r-l+1]%P+P)%P;
					if(!Hash.count(pre) || !Hash.count(suf))
						{
							++res[i];
							Hash[pre]=1;
							Hash[suf]=1;
						}
				}
			if(res[i]>maxx)
				maxx=res[i],tp=0;
			if(res[i]==maxx)
				ans[++tp]=i;
		}
	printf("%d %d
",maxx,tp);
    for(int i=1;i<=tp;i++) 
		printf("%d ",ans[i]);
    puts("");
	return 0;
}

Antisymmetry

  • 题意:定义反对称串是指满足取反后再前后翻转,恰好与原串相同的(01)串.现在给定一个(01)串,求出它的子串中反对称串的个数.

  • 不难发现,一个反对称串长度一定为偶数,且后半段取反后形成回文串.

  • 枚举每个位置作为对称中心,只用二分找出最大的半径长度.每次去掉两端的数后仍为反对称串,这个对称中心形成的共有半径长度个反对称串.

  • 检验时比较前半段(hash)值和后半段取反且逆向维护的(hash)值即可.

View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=5e5+10;
int n;
char s[MAXN];
typedef unsigned long long ull;
const ull Base=233;
ull Hash[MAXN],Pow[MAXN],revHash[MAXN];
LoveLive ans=0;
ull calchash(int l,int r,int type)
{
	if(!type)
		return Hash[r]-Hash[l-1]*Pow[r-l+1];
	else
		return revHash[l]-revHash[r+1]*Pow[r-l+1];
}
LoveLive solve(int x)
{
	int l=1,r=min(x,n-x);
	int res=0;
	while(l<=r)
		{
			int mid=(l+r)>>1;
			if(calchash(x-mid+1,x,0)==calchash(x+1,x+mid,1))
				res=mid,l=mid+1;
			else
				r=mid-1;
		}
	return 1LL*res;
}
int main()
{
	n=read();
	scanf("%s",s+1);
	Pow[0]=1;
	for(int i=1;i<=n;++i)
		{
			Pow[i]=Pow[i-1]*Base;
			Hash[i]=Hash[i-1]*Base+('1'-s[i]);
		}
	for(int i=n;i>=1;--i)
		revHash[i]=revHash[i+1]*Base+(('1'-s[i])^1);
	for(int i=1;i<=n;++i)
		ans+=solve(i);
	printf("%lld
",ans);
	return 0;
}

门票

  • 题意:给定一个一阶线性递推关系的数列,求出前(2e6)项中是否出现了循环.若有,输出开始循环的位置.数列中元素(leq 1e9).内存限制(4M).
  • 比较直接的想法是开(map)水过去,但大概率会(TLE),且超过了空间限制.
  • 做法是(hash),将出现过的元素模上大质数后记录.但这样直接压缩,显然极容易造成(hash)冲突.一个简单的办法是模两个大质数,双(hash)即可解决问题.
  • 另一个做法是离线,将前(2e6)个数全部算出来,离散化后处理.这样做每次都是严格(O(2e6cdot log(2e6)))的,可能会被卡常.但优点是有绝对严谨的正确性保证.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int P1=100049,P2=490001;
int vis[P2+10][2];
const int MAXT=2e6;
int a,b,c;
LoveLive A,B,C;
void solve()
{
	LoveLive res=1;
	vis[1][0]=vis[1][1]=-1;
	for(register int i=1;i<=MAXT;++i)
		{
			res=(A*res+res%B)%C;
			assert(res>=0);
			if(vis[res%P1][0]!=0 && vis[res%P1][0]==vis[res%P2][1])
				{
					printf("%d
",i);
					return;
				}
			if(!vis[res%P1][0])
				vis[res%P1][0]=i;
			if(!vis[res%P2][1])
				vis[res%P2][1]=i;
		}
	puts("-1");
}
int main()
{
	a=read(),b=read(),c=read();
	A=a,B=b,C=c;
	solve();
	return 0;
}

收集雪花

  • 题意:给(n)个数,求区间内数字都不重复的最大区间长度.元素大小(leq 1e9),(n leq 1e6).
  • 数据结构学多了使人变傻.
  • 首先需要离散化或(hash),将值域控制在(1e6)的级别.
  • 然后,若直接上主席树,每次二分答案,枚举左端点,是(O(nlog^2n))的,十分弱智.
  • 优秀的做法是(Two Pointers.)维护两个指针(l,r),不断往后跳,同时用类似于莫队的方法维护当前区间内颜色种类数目.合法时更新答案.
  • 这样每个指针最多跳(n)次,一共跳(2n)次,相当优秀.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
int n,x[MAXN],y[MAXN];
int cnt;
int t[MAXN];
int cols=0;
inline void ins(int pos)
{
	++t[x[pos]];
	if(t[x[pos]]==1)
		++cols;
}
inline void del(int pos)
{
	--t[x[pos]];
	if(t[x[pos]]==0)
		--cols;
}
int ans=0;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		y[i]=x[i]=read();
	sort(y+1,y+1+n);
	cnt=unique(y+1,y+1+n)-(y+1);
	for(int i=1;i<=n;++i)
		{
			x[i]=lower_bound(y+1,y+1+cnt,x[i])-y;
		}
	int l=1,r=1;
	for(;r<=n;++r)
		{
			ins(r);
			while(l<=r && (cols!=r-l+1))
				del(l++);
			if(cols==r-l+1)
				ans=max(ans,r-l+1);		
		}
	printf("%d
",ans);
	return 0;
}
## 小结 - 字符串 $Hash$ 在 $OI$ 中十分优秀,尤其是进制 $Hash$ .通过 $Hash$ ,我们可以将字符串比较是否相等的 $O(n)$ 降至 $O(1)$ ,这样以来,许多十分暴力的思想/做法也可以通过. - 离散化也可以算作是 $Hash$ 的一种,不过在转化的同时还要保证大小关系.
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jklover/p/10185164.html