一、题目：模拟散列表

840. 模拟散列表 - AcWing题库

分析 

代码（哈希表的拉链存储结构）

// 哈希表拉链法存储结构
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+3;
// 拉链结构
int h[N], e[N], ne[N], idx;void insert(int x) {int k = (x%N + N)%N; // 模加模是为了将负数余数变为整数e[idx]=x,ne[idx]=h[k],h[k]=idx++;
}bool find(int x) {int k = (x%N + N)%N;for(int i = h[k]; i != -1; i = ne[i]) {if(e[i] == x) return true; }return false;
}int main() {int n;cin >> n;memset(h,-1,sizeof h);while(n --) {char op; int x;cin >> op >> x;if(op == 'I') insert(x);else {if(find(x)) puts("Yes");else puts("No");}}return 0;
}

代码 （开放寻址存储结构）

#include<bits/stdc++.h>
using namespace std;const int N = 2e5+3, null = 0x3f3f3f3f;int h[N];int find(int x) {int k = (x%N + N)%N;// 坑位不空，且坑位不是查找值while(h[k]!=null && h[k]!=x) {k ++;if(k == N) k = 0; //往后坑位满了，循环到前面继续坑位}return k;
}int main() {int n;cin >> n;memset(h,0x3f,sizeof h);while(n --) {char op; int x;cin >> op >> x;// 返回坑位int k = find(x);if(op == 'I') h[k] = x;else {if(h[k]!=null) puts("Yes");else puts("No");}}return 0;
}

代码（stl——set）

#include<bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;set<int> a;while(n --) {char op;cin >> op;int x; cin >> x;if(op == 'I') a.insert(x);else {if (a.count(x)) puts("Yes");else puts("No");}}return 0;
}

二、题目：字符串哈希

841. 字符串哈希 - AcWing题库

 

代码1(string 的substr暴力）

TLE了 13个数据过11个

#include<bits/stdc++.h>
using namespace std;int n, m;
string s;int main() {cin >> n >> m;cin >> s;while(m --) {int l1,r1,l2,r2;cin >> l1 >> r1 >> l2 >> r2;string s1, s2;s1=s.substr(l1-1,r1-l1+1);s2=s.substr(l2-1,r2-l2+1);if(s1 == s2) puts("Yes");else puts("No");}return 0;
}

分析

代码2（字符串哈希）字符串前缀哈希法

#include<bits/stdc++.h>
using namespace std;typedef unsigned long long ull;
const int N = 1e5+10, P = 131; // 进制pint n, m;
char str[N];
ull h[N], p[N]; // 哈希表，和p底数表
// 取[l,r]区间哈希值
ull get(int l, int r) {return h[r] - h[l-1]*p[r-l+1];
}int main() {cin >> n >> m >> str+1; // 从1开始，不取0，因为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];}// 取两区间哈希值while(m --) {int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;if(get(l1,r1)==get(l2,r2)) puts("Yes");else puts("No");}return 0;
}