算法题整理——Hash

发表于 | 分类于 |

POJ3349_Snowflake Snow Snowflakes

描述

有n片雪花，每个雪花使用6个整数来描述其每个角。比如1，2，3，4，5，6，描述可以从任意一个角开始，比如上面的雪花也可以被描述为2，3，4，5，6，1，也可以是逆序的如3，2，1，6，5，4只要按一个圈来描述六个角就行。

现在，需要判断给出的雪花描述里面有没有相同的。

数据范围

0 < n ≤ 100000，雪花用正整数描述，小于10000000

思路

哈希做法，由于雪花的描述和顺序无关，我们构造和顺序无关的哈希函数，蓝书上的构造方法是这样的：

(∑ai + Πai) % P

其中ai表示雪花各个角的数字描述，P是一个大质数。

使用链表数组来存储雪花下标，以便于如果发现两片雪花的哈希值相等，我们可以进行进一步的比较。

这里，我取的P = 100003，从期望上来说，可以把每片不同的雪花分开。

比较使用的比较暴力的比较方法，轮转比较6次，再反向轮转比较6次，虽然很繁复，但考虑实际上比较的次数接近于常数次，所以比较的时间复杂度可以忽略。

整个算法接近于O(n)。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e6 + 5;
const int P = 1e6 + 3;

int a[N][6];
vector<int> hash[N];

int n;

bool check(int i, int j){
	int flag;
	for(int p = 0; p < 6; ++p){
		flag = 1;
		for(int k = 0; k < 6; ++k){
			if(a[i][k] != a[j][(k + p) % 6]){
				flag = 0;
				break;
			}
		}
		if(flag) return 1;
	}
	for(int p = 0; p < 6; ++p){
		flag = 1;
		for(int k = 0; k < 6; ++k){
			if(a[i][5 - k] != a[j][(k + p) % 6]){
				flag = 0;
				break;
			}
		}
		if(flag) return 1;
	}
	return 0;
}

int main(){
	scanf("%d", &n);
	fill(hash, hash + N, vector<int>{});
	for(int i = 0; i < n; ++i){
		scanf("%d %d %d %d %d %d", &a[i][0], &a[i][1], &a[i][2], &a[i][3], &a[i][4], &a[i][5]);
		long long mult = 1;
		int addt = 0;
		int pos = 0;
		for(int j = 0; j < 6; ++j){
			mult *= a[i][j];
			addt += a[i][j];
			mult %= P;
			addt %= P;
			pos = (mult + addt) % P;
		}
		for(int k = 0; k < hash[pos].size(); ++k){
			//printf("check(%d, %d)\n", i, hash[pos][k]);
			if(check(i, hash[pos][k])){
				printf("Twin snowflakes found.\n");
				return 0;
			}
		}
		hash[pos].push_back(i);
	}
	printf("No two snowflakes are alike.\n");
	return 0;
}

备注

在POJ上用C++提交会因为fill(hash, hash + N, vector < int > {})这句话报编译错误，可能不支持C++11，换成G++就好了。

因为mult没开long long而wa了几发。

CH1401_兔子与兔子

描述

有一个长度为S的小写字符串序列，查询Q次，每次指出两个区间，询问这两个区间内的字符串是否相等。

数据范围

1 <= S, Q <= 1e6

思路

朴素思想进行字符串比较的复杂度是O(QS)，使用字符串哈希的方法可以将复杂度降至大致为O(Q)。

字符串哈希的做法是这样的，首先给定一个数p，一般为131或1331（并不知道由来，只知道有这个传统），然后将字符串看作p进制数。

遍历字符串，每一位的哈希值等于上一位哈希值乘p加本位的字符值，再设置一个辅助数组，其第i位的值等于p的i次方。

以上操作均不处理溢出问题，权当取模。

这样，取出区间(l, r)哈希值的做法是：hashr - hashl-1 * pr-l+1

如果字符串的哈希值相等，我们认为它们相等，这里为了保险，我加上了还需要判断两个字符串长度一致。

据说实际上这种方法出现错误的概率还是很小的，如果担心出现问题，还可以设置多个p值，当多个p值下的哈希值都一致的情况下才认为相等。但对于这道题来说，p取131足够了。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e7 + 5;

char input[N];

int m, ll, lr, rl, rr;

int hash[N];
int p[N];

int main(){
	scanf("%s", input + 1);
	scanf("%d", &m);
	memset(hash, 0, sizeof(hash));
	int len = 0;
	hash[len] = 0;
	p[len] = 1;
	++len;
	for(; input[len]; ++len){
		hash[len] = hash[len - 1] * 131;
		hash[len] += input[len] - 'a';
		p[len] = p[len - 1] * 131;
	}
	
	/*for(int i = 0; i < len; ++i){
		printf("%d\n", hash[i]);
	}*/
	
	for(int i = 0; i < m; ++i){
		scanf("%d %d %d %d", &ll, &lr, &rl, &rr);
		int ret1 = hash[ll - 1] * p[lr - ll + 1] - hash[lr];
		int ret2 = hash[rl - 1] * p[rr - rl + 1] - hash[rr];
		if(ret1 == ret2 && lr - ll == rr - rl) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

POJ3974_Palindrome

描述

找出长度为N的字符串S的最长回文子串的长度。

数据范围

1 < N < 1e7

思路

回文数组有两种，长度为奇数的和长度为偶数的，长度为奇数的回文数组是以某个位置为中心，向两侧延申时对应位置的字符相等，长度为偶数的回文数组则是以中间两个字符的间隔为中心的。

可以通过遍历两次，第一次找出长度为奇数的最长回文数组，第二次找出长度为偶数的。

为了支持正序的子序列和逆序的子序列比对，需要建立一个正序子序列哈希数组，一个逆序哈希数组。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000000 + 5;

char input[N];

int hash1[N];
int hash2[N];
int p[N];
int len;

bool check(int l, int m1, int m2, int r){
	if(l == r) return 1;
	int ret1 = hash1[l - 1] * p[m1 - l + 1] - hash1[m1];
	int ret2 = hash2[len - r] * p[r - m2 + 1] - hash2[len - m2 + 1];
	return ret1 == ret2;
}

int main(){
	int con = 0;
	scanf("%s", input + 1);
	while(input[1] != 'E'){
		len = 0;
		hash1[0] = 0;
		p[0] = 1;
		++len;
		for(; input[len]; ++len){
			hash1[len] = hash1[len - 1] * 131 + input[len] - 'a';
			p[len] = p[len - 1] * 131;
		}
		
		hash2[0] = 0;
		for(int i = 1; i <= len; ++i){
			hash2[i] = hash2[i - 1] * 131 + input[len - i + 1] - 'a';
		}
		
		int ans1 = 0;
		for(int i = 1; i <= len; ++i){
			int l = 0;
			int r = min(len - i, i - 1);
			int mid = (l + r + 1) >> 1;
			while(l < r){
				if(check(i - mid, i, i, i + mid)) l = mid;
				else r = mid - 1;
				mid = (l + r + 1) >> 1;
			}
			ans1 = max(ans1, l);
		}
		
		int ans2 = 0;
		for(int i = 1; i < len; ++i){
			int l = 0;
			int r = min(len - i - 1, i - 1);
			int mid = (l + r + 1) >> 1;
			while(l < r){
				if(check(i - mid, i, i + 1, i + mid + 1)) l = mid;
				else r = mid - 1;
				mid = (l + r + 1) >> 1;
			}
			ans2 = max(ans2, l);
		}
		
		int ans = max(ans1 * 2 + 1, ans2 * 2 + 2);
		
		printf("Case %d: %d\n", ++con, ans);
		
		scanf("%s", input + 1);
	}
	return 0;
}