1. 哈希表
1-1. 介绍
本质上是一种高级的数组。原理是通过设计哈希函数将一些难以维护的值映射成为易于维护的值以加快查找速度。
但如果哈希函数设计的不够巧妙，可能会导致原本不同的值被映射成为了相同的值，即发生了冲突，可以使用以下两种方式解决问题：
1-1-1. 开散列法
对于每个存放位置的映射值开一个链表，每次插入在链表头插入，查询时遍历链表即可。
1-1-2. 闭散列法
这里介绍闭散列法中的线性探测法。
对于一个映射值 \(x\)，如果发生了冲突，就依次检查 \(x+1,x+2…\)。
1-2. 题目
1-2-1. POJ-3349 Snowflake Snow Snowflakes
题面描述
分析
对于一个雪花，它不同的有序形态有 \(12\) 种，那么暴力的思路就是每次将这 \(12\) 种形态全部放入一个哈希表中进行维护，时间复杂度 \(O(12n)\)，可以通过本题。
当然也可以只向哈希表中插入一种形态，而将查询进行 \(12\) 次。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Node {
int a[6];
bool operator==(const Node &tmp) const {
for (int i=0; i<6; i++) if (a[i]!=tmp.a[i]) return false;
return true;
}
};
struct NodeHash {
size_t operator()(const Node &tmp) const {
unsigned long long res=1;
for (int i=0; i<6; i++) res*=tmp.a[i];
return res;
}
};
int n;
int a[6];
unordered_set<Node,NodeHash> s;
inline Node work(int p,int d) {
Node res;
for (int i=0; i<6; i++)
res.a[i]=a[(p+i*d+n)%6];
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
bool flag=false;
for (int i=1; i<=n; i++) {
for (int i=0; i<6; i++) cin>>a[i];
for (int i=0; i<6; i++) {
if (s.find(work(i,+1))!=s.end()) {flag=true; break;}
if (s.find(work(i,-1))!=s.end()) {flag=true; break;}
}
s.insert(work(0,+1));
}
if (flag) puts("Twin snowflakes found.");
else puts("No two snowflakes are alike.");
return 0;
}
2. 树哈希
2-1. 介绍
经常用来判断一些树是否同构。
对于两颗树 \(T_1,T_2\)，如果能够通过将 \(T_1\) 的所有节点重新编号，使得树 \(T_1\) 和 \(T_2\) 完全相同，那么称两颗树同构。
2-2. 题目
2-2-1. POJ-1635 Subway tree systems
题面描述
给定两个树的括号序，判断两颗树是否同构。
分析
树哈希模板题。
树哈希函数设计为子树哈希值排序后拼接。
时间复杂度 \(O(nlogn)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3005,base=13331;
int p,cnt,len;
char s[N];
ull dfs() {
ull res=;
p++;
vector<ull> son;
while (p<=len && s[p]=='0') son.push_back(dfs());
sort(son.begin(),son.end());
p++;
for (ull x:son) res=res*base+x;
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin>>T;
while (T--) {
cin>>(s+1);
len=strlen(s+1);
p=0; ull h1=dfs();
cin>>(s+1);
if (len!=strlen(s+1)) {puts("different"); continue;}
p=0; ull h2=dfs();
if (h1==h2) puts("same");
else puts("different");
}
return 0;
}
2-2-2. Luogu-P8499 [NOI2022] 挑战 NPC Ⅱ
题面描述
分析
由题意得，正解可能是哈希，题中又要求我们判断两颗树是否同构，于是考虑树哈希。
因为两个树最多相差 \(5\) 个点，所以这两颗树会有一部分是不需要进行任何操作就同构的，于是我们将这些部分删除。
这时两树剩余的节点减少，我们可以直接通过暴力枚举来判断答案。
时间复杂度上界 \(O(n\prod_{i=1}^ki!)\)，经测试通过剪枝表现不错，可以通过本题。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+5,base=131;
inline bool cmp1(int a,int b);
inline bool cmp2(int a,int b);
int k;
ull pw[N*2];
struct Tree {
int n,rt,edgeCnt;
int head[N],siz[N];
ull h[N];
struct Edge {int v,nxt;} edge[N];
inline void init() {
edgeCnt=0;
for (int i=1; i<=n; i++) head[i]=0;
}
inline void addEdge(int u,int v) {
edge[++edgeCnt]=(Edge){v,head[u]};
head[u]=edgeCnt;
}
void dfs(int u,int id) {
siz[u]=1; h[u]='(';
vector<int> son;
for (int i=head[u]; i; i=edge[i].nxt) {
int v=edge[i].v;
dfs(v,id);
son.push_back(v);
siz[u]+=siz[v];
}
if (id==1) sort(son.begin(),son.end(),cmp1);
else sort(son.begin(),son.end(),cmp2);
for (int x:son) h[u]=h[u]*pw[siz[x]*2]+h[x];
h[u]=h[u]*base+')';
}
} t1,t2;
inline bool cmp1(int a,int b) {return t1.h[a]<t1.h[b];}
inline bool cmp2(int a,int b) {return t2.h[a]<t2.h[b];}
map<int,bool> mp[N];
bool dfs(int u1,int u2) {
if (t1.siz[u1]<t2.siz[u2] || (t1.siz[u1]==t2.siz[u2] && t1.h[u1]!=t2.h[u2])) return false;
if (mp[u1].find(u2)!=mp[u1].end()) return mp[u1][u2];
vector<int> son1,son2;
for (int i=t1.head[u1]; i; i=t1.edge[i].nxt) son1.push_back(t1.edge[i].v);
for (int i=t2.head[u2]; i; i=t2.edge[i].nxt) son2.push_back(t2.edge[i].v);
sort(son1.begin(),son1.end(),cmp1);
sort(son2.begin(),son2.end(),cmp2);
int n=son1.size(),m=son2.size();
int p=0,q=0;
vector<int> dif1,dif2;
while (p<n && q<m) {
while (q<m && t2.h[son2[q]]<t1.h[son1[p]]) {dif2.push_back(son2[q]); q++;}
if (q<m) if (t1.h[son1[p]]==t2.h[son2[q]]) p++,q++;
else {dif1.push_back(son1[p]); p++;}
}
while (p<n) dif1.push_back(son1[p++]);
while (q<m) dif2.push_back(son2[q++]);
n=dif1.size(),m=dif2.size();
if (n<m || n-m>k) return mp[u1][u2]=false;
if (dif1.size()-dif2.size()>k) return mp[u1][u2]=false;
sort(dif1.begin(),dif1.end());
do {
bool flag=true;
for (int i=0; i<m; i++)
if (t1.siz[dif1[i]]<t2.siz[dif2[i]]
|| (t1.siz[dif1[i]]==t2.siz[dif2[i]]
&& t1.h[dif1[i]]!=t2.h[dif2[i]])) {flag=false; break;}
if (!flag) continue;
for (int i=0; i<m; i++)
if (!dfs(dif1[i],dif2[i])) {flag=false; break;}
if (flag) return mp[u1][u2]=true;
} while (next_permutation(dif1.begin(),dif1.end()));
return mp[u1][u2]=false;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int C,T,K; cin>>C>>T>>K;
pw[0]=1; for (int i=1; i<=1e5; i++) pw[i]=pw[i-1]*base;
while (T--) {
cin>>t1.n;
t1.init();
for (int i=1; i<=t1.n; i++) {
int x; cin>>x;
if (x==-1) t1.rt=i;
else t1.addEdge(x,i);
mp[i].clear();
}
t1.dfs(t1.rt,1);
cin>>t2.n;
t2.init();
for (int i=1; i<=t2.n; i++) {
int x; cin>>x;
if (x==-1) t2.rt=i;
else t2.addEdge(x,i);
}
k=t1.n-t2.n;
t2.dfs(t2.rt,2);
if (dfs(t1.rt,t2.rt)) puts("Yes");
else puts("No");
}
return 0;
}
3. 字符串哈希
3-1. 介绍
通过设计哈希函数将一个字符串映射成为一个整数。
3-2. 题目
3-2-1. Acwing-138 兔子与兔子
题面描述
给定长为 \(n\) 的字符串和 \(m\) 次询问，每次询问串中 \([l_1,r_1]\) 和 \([l_2,r_2]\) 两个区间构成的字符串是否相等。
\(1\le n,m\le10^6\)。
分析
字符串哈希模板题。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+5,base=131;
int n;
ull pw[N],h[N];
char s[N];
inline ull getHash(int l,int r) {return h[r]-h[l-1]*pw[r-l+1];}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>(s+1);
n=strlen(s+1);
pw[0]=1;
for (int i=1; i<=n; i++) {
pw[i]=pw[i-1]*base;
h[i]=h[i-1]*base+s[i];
}
int q; cin>>q;
while (q--) {
int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;
if (getHash(l1,r1)==getHash(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
}
3-2-2. POJ-3974 Palindrome
题面描述
给定长为 \(n\) 的字符串，求其最长回文字串长度。
\(1\le n\le10^6\)
分析
可以通过枚举回文串中点+二分答案的方法在 \(O(nlogn)\) 时间内解决问题。不过这里介绍 \(O(n)\) 的另一种做法。
记 \(R_i\) 表示以 \(i\) 作为结尾的最长回文子串的长度。通过定义可以得到 \(R_i\le R_{i-1}+2\)，因此我们可以以 \(R_{i-1}+2\) 作为答案上界来枚举 \(R_i\) 的值。
因为 \(R_i\) 每次只会比 \(R_{i-1}\) 大 \(2\)，总共增加 \(n\) 次，所以暴力枚举 \(R_i\) 只会执行 \(2n\) 次，时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+5,base=131;
int n;
int R[N];
ull pw[N],h1[N],h2[N];
char s[N];
inline ull gh1(int l,int r) {return h1[r]-h1[l-1]*pw[r-l+1];}
inline ull gh2(int l,int r) {return h2[r]-h2[l-1]*pw[r-l+1];}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=0;
pw[0]=1;
for (int i=1; i<=1e6; i++) pw[i]=pw[i-1]*base;
while (true) {
T++;
cin>>(s+1); n=strlen(s+1);
if (s[1]=='E') break;
for (int i=1; i<=n; i++) {
h1[i]=h1[i-1]*base+s[i];
h2[i]=h2[i-1]*base+s[n-i+1];
}
R[1]=1;
for (int i=2; i<=n; i++) {
int tmp=R[i-1]+2;
while (tmp>1) {
if (i-tmp+1<1) {tmp--; continue;}
if (gh1(i-tmp+1,i-tmp+(tmp+1)/2)==gh2(n-i+1,n-i+(tmp+1)/2)) break;
tmp--;
}
R[i]=tmp;
}
int ans=1;
for (int i=1; i<=n; i++) ans=max(ans,R[i]);
cout<<"Case "<<T<<": "<<ans<<'\n';
}
return 0;
}
3-2-3. Acwing-160 匹配统计
题面描述
分析
对于每个 A 串的前缀，二分哈希求最长匹配即可。
时间复杂度 \(O(nlogn)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5,base=131;
int n,m,q;
int ans[N],cnt[N];
ull pw[N],h1[N],h2[N];
char s[N],t[N];
inline ull gh1(int l,int r) {return h1[r]-h1[l-1]*pw[r-l+1];}
inline ull gh2(int l,int r) {return h2[r]-h2[l-1]*pw[r-l+1];}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
cin>>(s+1)>>(t+1);
pw[0]=1;
for (int i=1; i<=n || i<=m; i++) pw[i]=pw[i-1]*base;
for (int i=1; i<=n; i++) h1[i]=h1[i-1]*base+s[i];
for (int i=1; i<=m; i++) h2[i]=h2[i-1]*base+t[i];
for (int i=1; i<=n; i++) {
int l=1,r=min(n,m);
while (l<=r) {
int mid=l+r>>1;
if (gh1(i,i+mid-1)==gh2(1,mid)) ans[i]=mid,l=mid+1;
else r=mid-1;
}
cnt[ans[i]]++;
}
while (q--) {
int x; cin>>x;
cout<<cnt[x]<<'\n';
}
return 0;
}