hash，ACM集训

                                840. 模拟散列表

目录

                                840. 模拟散列表

输入格式

输出格式

数据范围

输入样例：

输出样例：

 解析：

                                841. 字符串哈希

输入格式

输出格式

数据范围

输入样例：

输出样例：

 解析：字符串前缀hash法

                        4696. 最长回文

输入格式

输出格式

数据范围

输入样例：

输出样例：

 解析：字符串hash；二分+hash；队列和栈；Manacher算法

---

840. 模拟散列表 - AcWing题库

维护一个集合，支持如下几种操作：

1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤105
−109≤x≤109

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

 解析：

拉链法代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int N = 1e5 + 3;
int n;
int h[N], e[N], ne[N], ind;
 
void Insert(int a) {
	int t = (a % N + N) % N;
	e[ind] = a, ne[ind] = h[t], h[t] = ind++;
}
 
int find(int a) {
	int t = (a % N + N) % N;
	for (int i = h[t]; i != -1; i = ne[i])
		if (e[i] == a)
			return 1;
	return 0;
}
 
int main() {
	cin >> n;
	char op[2];
	int t;
	memset(h, -1, sizeof(h));
	for (int i = 1; i <= n; i++) {
		scanf("%s%d", op, &t);
		if (op[0] == 'I') {
			Insert(t);
		}
		else {
			if (find(t))
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
	}
	return 0;
}

开放寻址法 通常数组大小要开到2到3倍（经验之谈）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int N = 3e5 + 5,null=0x3f3f3f3f;
int n;
int h[N];
 
int find(int a) {
	int k = (a % N + N) % N;
	while (h[k]!=null&&h[k]!=a) {
		k++;
		if (k == N)k = 0;
	}
	return k;
}
 
int main() {
	cin >> n;
	char op[2];
	int t;
	memset(h, 0x3f, sizeof(h));
	for (int i = 1; i <= n; i++) {
		scanf("%s%d", op, &t);
		int k = find(t);
		if (op[0] == 'I') {
			h[k] = t;
		}
		else {
			if (h[k] == null)
				cout << "No" << endl;
			else
				cout << "Yes" << endl;
		}
	}
	return 0;
}

                                841. 字符串哈希

 841. 字符串哈希 - AcWing题库

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

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

输出样例：

Yes
No
Yes

 解析：字符串前缀hash法

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 5,P=131;
int n, m;
char str[N];
ULL h[N], p[N];
 
ULL get(int l, int r) {
	return h[r] - h[l-1] * p[r - l + 1];
}
 
int main() {
	scanf("%d%d%s", &n, &m, str + 1);
	p[0] = 1;
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + str[i];
	}
	int l1, r1, l2, r2;
	while (m--) {
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (get(l1, r1) == get(l2, r2)) {
			cout << "Yes" << endl;
		}
		else
			cout << "No" << endl;
	}
	return 0;
}

                        4696. 最长回文

4696. 最长回文 - AcWing题库

给出一个只由小写英文字符 a,b,c…y,z 组成的字符串 S，求 S 中最长回文串的长度。

回文就是正反读都是一样的字符串，如 aba, abba 等。

输入格式

输入有多组测试数据，不超过 120 组。

每组输入为一行小写英文字符 a,b,c…y,z 组成的字符串 S

两组数据之间由空行隔开(该空行不用处理)。

输出格式

每一行一个整数 x，对应一组数据，表示该组数据的字符串中所包含的最长回文长度。

数据范围

1≤|S|≤110000

输入样例：

aaaa
 
abab

输出样例：

4
3

 解析：字符串hash；二分+hash；队列和栈；Manacher算法

字符串hash法：

将两个hash数组，一个正着hash，另一个反着hash

 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 1e4 + 5,P=131;
char str[N];
ULL h[N],h1[N], p[N];
 
ULL get(int l, int r, ULL* arr) {
	return arr[r] - arr[l - 1] * p[r - l + 1];
}
 
int main() {
	while (scanf("%s", str + 1) != EOF) {
		int n = strlen(str + 1);
		p[0] = 1;
		for (int i = 1,j=n; i <= n;j--, i++) {
			p[i] = p[i - 1] * P;
			h[i] = h[i - 1] * P + str[i];
			h1[i] = h1[i - 1] * P + str[j];
		}
		int len1 = 1, len2 = 1;
		for (int i = 1; i <= n; i++) {
			while (i - len1 >= 1 && i + len1 <= n && (get(i - len1, i, h) == get(n-i-len1+1,n-i+1, h1))) {
				len1++;
			}
			while (i - len2 >= 0 && i + len2 <= n && (get(i - len2 + 1, i, h) == get(n-i-len2+1,n-i, h1))) {
				len2++;
			}
		}
		cout << max(len2 * 2 - 2, len1 * 2 - 1) << endl;
	}
	return 0;
}

这是我一开始的错误代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 1e4 + 5, P = 131;
 
ULL h[N], h1[N], p[N];
string str, str1;
 
ULL get(int l, int r, ULL* arr) {
	return arr[r] - arr[l] * p[r - l];
}
 
int main() {
	while (cin >> str) {
		int n = str.length();
		str1 = str;
		reverse(str1.begin(), str1.end());
		str.insert(0, " ");
		str1.insert(0, " ");
		p[0] = 1;
		for (int i = 1; i <= n; i++) {
			p[i] = p[i - 1] * P;
			h[i] = h[i - 1] * P + str[i];
			h1[i] = h1[i - 1] * P + str1[i];
		}
		int mx = 1;
		for (int i = 0; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				if (get(i, j, h) == get(n - j, n - i, h1))
					mx = max(mx, j - i);
			}
		}
		cout << mx << endl;
	}
	return 0;
}

这个代码最大的缺陷就是这个代码是从左到右延申，到实际上如果从中间像两头延申的话当出现不满足的情况时就和以确定以i为中心的最长的回文子串的长度了，没有必要继续判断以i为中心是否有更长的回文子串了