算法竞赛进阶指南 基础数据结构 hash

Hash 表

hash表主要包括以下基本操作 

1.计算hash函数的值

2.定位到对应链表中依次遍历，比较。

P10467 [CCC 2007] Snowflake Snow Snowflakes

时间限制: 1.00s    内存限制: 512.00MB

 复制 Markdown

 中文

 退出 IDE 模式

题目描述

你可能听说过没有两片雪花是相同的。你的任务是编写一个程序来确定这是否真的是正确的。你的程序将读取关于一组雪花的信息，并搜索可能相同的一对雪花。每片雪花有六条“角”。对于每片雪花，你的程序将提供每条角的长度测量。任何一对长度对应的角相同的雪花都应该被你的程序标记为可能相同。

输入格式

输入的第一行包含一个整数 n，0<n≤100000，表示接下来的雪花数量。接下来的 n 行描述每片雪花。每片雪花由包含六个整数的一行描述（每个整数至少为 0 且小于 10000000），表示雪花的六条角的长度。角的长度将按顺序围绕着雪花给出（顺时针或逆时针），但它们可以从六个角中的任何一条开始。例如，同一片雪花可以描述为 1 2 3 4 5 6 或 4 3 2 1 6 5。

输出格式

如果所有的雪花都是不同的，你的程序应该打印消息：

No two snowflakes are alike.

如果有一对可能相同的雪花，你的程序应该打印消息：

Twin snowflakes found.

翻译来自于：ChatGPT

显示翻译

题意翻译

输入输出样例

输入 #1复制运行

2 
1 2 3 4 5 6 
4 3 2 1 6 5

输出 #1复制运行

Twin snowflakes found.

定义一个hash函数 计算hash值为六个数字之和加六个数字之积  对于相同的雪花他们的hash值一定相同    建立一个hash表 将雪花依次插入  对于每片雪花  我们都扫描表头对应的链表  检查是否存在相同的雪花  相同输出 结束程序  不同则插入 继续进行知道结束

每个head指向每个hash值的一个头元素 然后他的next存储了这个链表（这个hash值）的其他雪花 通head找到头 然后通过next访问整个链表   每次插入的时候插入到链表的头部  然后更新next

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,tot,snow[N][6],head[N],nex[N];
const int mod =99991;
int H(int *a){
	int sum=0,mul=1;
	for(int i=0;i<6;i++){
		sum=(sum+a[i])%mod;
		mul=1LL*mul*a[i]%mod;
	}
	return (sum+mul)%mod;
}
bool equal(int *a,int *b){
	for(int i=0;i<6;i++){
		for(int j=0;j<6;j++){
			bool eq=1;
			for(int k=0;k<6;k++)
				if(a[(i+k)%6]!=b[(j+k)%6])eq=0;
			if(eq)return 1;
			eq=1;
			for(int k=0;k<6;k++)
				if(a[(i+k)%6]!=b[(j-k+6)%6])eq=0;
			if(eq)return 1;
		}
	}
	return 0;
}
bool insert(int *a){
	int val =H(a);
	for(int i=head[val];i;i=nex[i]){
		if(equal(snow[i],a))return 1;
	}
	++tot;
	memcpy(snow[tot],a,6*sizeof(int));
	nex[tot]=head[val];
	head[val]=tot;
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a[10];
		for(int j=0;j<6;j++)cin>>a[j];
		if(insert(a)){
			cout<<"Twin snowflakes found."<<endl;
			return 0;
		}
	}
	cout<<"No two snowflakes are alike.";
	return 0;
}

还有一种最小表示法的优化方法  暂时未给出 

字符串 Hash

字符串hash把一个任意长度的字符串映射成一个非负整数 并且冲突的概率几乎为 0；

取一个固定值p，把字符串看作为一个p进制数并且分配一个大于0 的数值 ，代表每种字符；一般来说我们分配的数值都远小于p  例如小写字母构成的字符串  可以令a-z分别为1到26  取一个固定值M求出该p进制数对M的余数作为hash值 

一般来说 p取131   13331 此时hash值产生冲突的概率极低  通常我们取一个较大的质数为M  或者取M=2^64 也就是usigned long long  在计算不处理算数溢出的问题的时候 产生溢出直接对这个取模  可以避免低效的取模运算；

对于字符串的各种操作 我们都可以反应到hash值来

如果hash值为h(s)  那么在字符串s后面加上字符c  他的hash值即为H(s+c)=(H(s)*p+value[c])mod M  也就是进制左移  加上c代表的数值

如果知道了s的hash和s+t的hash值  那么我们也可以求t的hash值 ： H(T)=(H(s+t)-H(s)*p^length(t)) mod M  。  相当于在p进制下左移s的hash值使得s与s+t的左端对齐  那么相减后就是t的hash值

计算某一段的hash值：
首先 最暴力的也就是从这一段的起始遍历到末尾 然后模拟进制    但是很暴力  很容易导致tle

long long H(int l,int r){
	long long ans=0;
	for(int i=l;l<=r;l++){
		ans=(ans*p+(s[i]-'a'))%mod;
	}
	return ans;
}

第二种做法

预处理后运用类似于前缀和的思想进行计算：                                                                                 

ULL H(int l,int r){ //获得l r 段的hash值 r段的hash减去l-1段的hash移位  移动到与r最高位对齐
	return h[r] - h[l - 1] * power[r - l + 1];	//移动后的总长度为r所以后段与进位的索引和也为r
}
//预处理
char str[N];
scanf("%s",str+1);
int n=strlen(str+1);
power[0]=1;
for(int i=1;i<=n;i++){
	h[i]=h[i-1]*p+str[i]-'a'+1;	//计算从开头到当前的字符的hash
	power[i]=power[i-1]*p;		//计算进位
}

P10468 兔子与兔子

时间限制: 1.00s    内存限制: 512.00MB

 复制 Markdown 退出 IDE 模式

题目描述

很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。

然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。

注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式

第一行输入一个 DNA 字符串 S。

第二行一个数字 m，表示 m 次询问。

接下来 m 行，每行四个数字 l1​,r1​,l2​,r2​，分别表示此次询问的两个区间，注意字符串的位置从 1 开始编号。

输出格式

对于每次询问，输出一行表示结果。

如果两只兔子完全相同输出  Yes，否则输出  No（注意大小写）。

输入输出样例

输入 #1复制运行

aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2

输出 #1复制运行

Yes
No
Yes

说明/提示

数据保证，1≤∣S∣,m≤106。其中，∣S∣ 为字符串 S 的长度。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int p=131;
const int mod =23333,N=1e6+5;
ULL h[N], power[N];
char str[N];
ULL H(int l,int r){ //获得l r 段的hash值 r段的hash减去l-1段的hash移位  移动到与r最高位对齐
	return h[r] - h[l - 1] * power[r - l + 1];	//移动后的总长度为r所以后段与进位的索引和也为r
}
int main() {
	scanf("%s",str+1);
	int n=strlen(str+1);
	power[0]=1;
	int m;cin>>m;
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*p+str[i]-'a'+1;	//计算从开头到当前的字符的hash
		power[i]=power[i-1]*p;		//计算进制
	}
	for(int i=1,l1,r1,l2,r2;i<=m;i++){
		cin>>l1>>r1>>l2>>r2;
		if(H(l1,r1)==H(l2,r2))cout<<"Yes
";
		else cout<<"No
";
	}
	return 0;
}

P1210 [USACO1.3] 最长的回文 Calf Flac

时间限制: 1.00s    内存限制: 125.00MB

 复制 Markdown

 中文

 退出 IDE 模式

题目描述

据说如果你给无限只母牛和无限台巨型便携式电脑（有非常大的键盘 ), 那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观（最棒的回文）。

在寻找回文时不用理睬那些标点符号、空格（但应该保留下来以便做为答案输出）, 只用考虑字母 A∼Z 和 a∼z。要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字符串。我们将保证最长的回文不会超过 2,000 个字符（在除去标点符号、空格之前）。

输入格式

输入文件不会超过 20,000 字符。这个文件可能一行或多行，但是每行都不超过 80 个字符（不包括最后的换行符）。

输出格式

输出的第一行应该包括找到的最长的回文的长度。

下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。

如果有多个回文长度都等于最大值，输出最前面出现的那一个。

输入输出样例

输入 #1复制运行

Confucius say: Madam, I'm Adam. 

输出 #1复制运行

11
Madam, I'm Adam

说明/提示

题目翻译来自NOCOW。

USACO Training Section 1.3

朴素算法  直接枚举每个位置  为中心  然后向两边延申  相同的话就长度加2    记录字符串的起始和末尾然后输出即可  缺点就是时间复杂度比较高

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,l,at[N],last;  //at保存新的字符在原来的字符的映射；
char k[N],m[N];
int get(int n){
	int a1=1,a2=0;
	for(int i=n,j=1;i-j>=0&&i+j<l&&m[i-j]==m[i+j];j++)a1+=2;
	for(int i=n,j=0;i-j>=0&&i+1+j<l&&m[i-j]==m[i+j+1];j++)a2+=2;
	return max(a1,a2);
}
int main() {
	while((k[n]=getchar())!=EOF)n++;
	for(int i=0;i<n;i++){
		if(isalpha(k[i])){
			m[l]=tolower(k[i]);at[l++]=i;
		}
	}
	int ans=0;
	for(int i=0;i<l;i++){
		int t=get(i);
		if(t>ans){
			ans=t;
			last=i+(t/2);
		}
	}
	k[at[last]+1]='';
	printf("%d
%s
",ans,&k[at[last-ans+1]]);
	return 0;
}

算法竞赛进阶指南 中书上的例题并没有字符 并且全为小写   所以后续的hash做法用书上的题进行演示  

这里给出题目

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。

输入格式

输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 1000000 个小写字符的形式给出。

输入以一个以字符串  END 开头的行表示输入终止。

输出格式

对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

如果一个字符串是回文字符串 那么他左边部分的hash与右边部分的倒序的hash值是一样的 那么我么依旧可以枚举每个中心点进行  但是与上面不同的是 我们可以预处理前缀hash值和后缀hash值 然后直接二分查找 寻找最长子段  而不是一一判断 这样的效率更高 适合高数据量的情况 

小技巧  对于奇数的回文字符串 我们可以枚举中心点  但是对于偶数的回文字符串  他没有中心字符串  那么对于这种情况 我们可以在一个字符串中两两字符之前加上一个特殊字符#（也可以不是# 这里方便演示）  对于奇数来说 加上后仍然是奇数  偶数就会变成奇数 这样就避免了偶数没有中心的问题  通过枚举每个中心点就可以同时解决奇数和偶数的问题

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=2e6+5,base =131;
char str[N];
ULL hl[N],hr[N],p[N];
ULL get(ULL h[],int l,int r){    //计算hash值
	return h[r]-h[l-1]*p[r-l+1];
}
int main() {
	int T=1;
	while(scanf("%s",str+1),strcmp(str+1,"END")){	//读入字符串
		int n=strlen(str+1);
		//预处理 在每两个字符串中加上特殊字符 使得偶数 奇数回文长度都化为奇数处理 简化操作
		for(int i=n*2;i;i-=2){
			str[i]=str[i/2];	//将偶数位变成原字符  
			str[i-1]='a'+26;	//奇数位变为特殊字符
		}
		n*=2;
		p[0]=1;
		for(int i=1,j=n;i<=n;i++,j--){
			hl[i]=hl[i-1]*base+str[i]-'a'+1; //正序前缀hash
			hr[i]=hr[i-1]*base+str[j]-'a'+1; //逆序后缀hash
			p[i]=p[i-1]*base;				 //幂次
		}
		int res=0;
		for(int i=1;i<=n;i++){	//枚举回文中心
			int l=0,r=min(i-1,n-i);//二分的最大半径 (到起点距离和到终点距离的最小值)
			while(l<r){
				int mid = l+r+1>>1;
				if(get(hl,i-mid,i-1)!=get(hr,n-(i+mid)+1,n-(i+1)+1))    //左半==右半
					r=mid -1 ;
				else l=mid;
			}
			if(str[i-l]<='z')res=max(res,l+1);    //判断这一位置是特殊字符还是字母
			else res=max(res,l);
		}
		printf("Case %d: %d
", T ++ , res);
	}
	return 0;
}

P10469 后缀数组

时间限制: 2.00s    内存限制: 512.00MB

 复制 Markdown 退出 IDE 模式

题目描述

后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者 DC3 算法实现，这超出了我们的讨论范围。

在本题中，我们希望使用快排、Hash 与二分实现一个简单的 O(nlog2n) 的后缀数组求法。

详细地说，给定一个长度为 n 的字符串 S（下标 0∼n−1），我们可以用整数 k(0≤k<n) 表示字符串 S 的后缀 S(k∼n−1)。

把字符串 S 的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。

额外地，我们考虑排名为 i 的后缀与排名为 i−1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。

我们的任务就是求出 SA 与 Height 这两个数组。

输入格式

输入一个字符串，其长度不超过 30 万。

字符串由小写字母构成。

输出格式

第一行为数组 SA，相邻两个整数用 1 个空格隔开。

第二行为数组 Height，相邻两个整数用 1 个空格隔开，我们规定 Height[1]=0。

输入输出样例

输入 #1复制运行

ponoiiipoi

输出 #1复制运行

9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

对于这道题  我们要先对每个后缀进行字典序排序  然后要求出排序后的相邻项的最大公共前缀  那么字典序排序的时候 我们就可以直接先算出两个后缀的最长公共前缀的长度 然后加上去  直接比较不同的部分的字符 就可以得到字典序排序  然后排完序后  再求最大前缀   那么我们要解决的问题就是求最长公共前缀  这个过程我们可以用 hash+二分 实现先预处理一下hash值 然后要求两个前缀的公共长度的时候我们可以直接以他们为起点然后二分找到一段字符串判断hash值是否相等   直到找到最长的长度 这样就ok了

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef unsigned long long ULL;
ULL f[N],power[N];    //hash  进制
int sa[N],height[N],n;    //后缀的首字母的序号  
char str[N];
ULL get(int l,int r){        //获取hash
	return f[r]-f[l-1]*power[r-l+1];
}
int lcp(int x,int y){    //计算最长公共前缀
	int l=0,r=min(n-x+1,n-y+1);    //最长的长度为两个后缀到结尾的最短长度
	while(l<r){
		int mid = (l+r+1)>>1;    //由于答案分布在左侧 所以防止死循环
		if(get(x,x+mid-1)==get(y,y+mid-1))l=mid;
		else r=mid -1;
	}
	return l;
}
bool cmp(int x,int y){    //字典序排序  算出公共的部分 然后直接比较不同的部分
	int l=lcp(x,y);
	return str[x+l]<str[y+l];
}
int main() {
	scanf("%s",str+1);
	n=strlen(str+1);
	power[0]=1;
	for(int i=1;i<=n;i++){    //hash预处理
		sa[i]=i;
		f[i]=f[i-1]*131+(str[i]-'a'+1);
		power[i]=power[i-1]*131;
	}
	sort(sa+1,sa+1+n,cmp);    /排序
	for(int i=2;i<=n;i++){
		height[i]=lcp(sa[i-1],sa[i]);    //计算邻项的公共前缀
	}
	for(int i=1;i<=n;i++)printf("%d ", sa[i]-1); puts("");
	for(int i=1;i<=n;i++)printf("%d ", height[i]); puts("");
	cout<<endl;
	return 0;
}