hash总结（个人笔记）
柒葉灬
2018-12-27 22:23:22
# $hash$专题总结
------
$Hash$不用过多讲了，就是将**状态**映射成一个**数字**，其中数字本质上就是$K$进制数，$K≥$ 状态数 。
------------
$hash$ 需要一个$base$（与进制），和一个模数 $P$（拼人品），其中$base$**必须要大于等于状态数**。不然如果发生了进位那么就没有意义了。
>还是例题更能说明问题
-----
[例题 专题A](https://cn.vjudge.net/contest/277011#problem/A)
**题意**：给三个字符串，问是否存在一个字符串，满足同时是三个字符串的子串，如果有则输出最长长度，否则输出$0$。
**思路**：先要二分，因为显然满足带调性，接下来就是$hash$了，把第一个字符串所有长度为$K$的放进$set$里面，然后...（略）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5,base=31,P=1e9+9;
set<int>s1,s2;
int Pow[maxn];
void init(){
Pow[0]=1;
for(int i=1;i<maxn;i++)
Pow[i]=1LL*Pow[i-1]*base%P;
}
struct String{
char str[maxn];
int n,sum[maxn];
int Query(int l,int r){
return (sum[r]-1LL*sum[l-1]*Pow[r-l+1]%P+P)%P;
}
void read(){
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)
sum[i]=(1LL*sum[i-1]*base+str[i]-'a')%P;
}
void add1(int x){
for(int i=x;i<=n;i++)
s1.insert(Query(i-x+1,i));
}
void add2(int x){
for(int i=x;i<=n;i++){
int tmp=Query(i-x+1,i);
if(s1.find(tmp)!=s1.end())
s2.insert(tmp);
}
}
bool find(int x){
for(int i=x;i<=n;i++)
if(s2.find(Query(i-x+1,i))!=s2.end())return true;
return false;
}
}A,B,C;
bool check(int x){
s1.clear();s2.clear();
A.add1(x);B.add2(x);
return C.find(x);
}
int main(){
init();
int QuQ;cin>>QuQ;
for(int cas=1;cas<=QuQ;cas++){
A.read();B.read();C.read();
int l=1,r=min(A.n,min(B.n,C.n)),ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
printf("Case %d: %d\n",cas,ans);
}
return 0;
}
```
------
[例题 专题B](https://cn.vjudge.net/contest/277011#problem/B)
**思路**：因为$2$ 个 $hash$的数值加起来要正好满足$10$进制，所以$base$必须是$10$，同时枚举等号时也就可以大致确定加号位置。（个位数+个位数！=百位数）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,ansa,ansb;
char str[maxn];
struct Hash{
int sum[maxn],f[maxn],base,P;
void init(int Bas,int Pi){
base=Bas;P=Pi;
for(int i=1;i<=n;i++)
sum[i]=(1LL*sum[i-1]*base+str[i]-'0')%P;
f[0]=1;
for(int i=1;i<maxn;i++)
f[i]=1LL*f[i-1]*base%P;
}
int solve(int l,int r){
return (sum[r]-1LL*sum[l-1]*f[r-l+1]%P+P)%P;
}
}hash1,hash2;
struct node{
int a,b;
void operator +=(const node &_){
a=(a+_.a)%hash1.P;
b=(b+_.b)%hash2.P;
}
bool operator ==(const node &_)const{
return a==_.a&&b==_.b;
}
void solve(int l,int r){
a=hash1.solve(l,r);
b=hash2.solve(l,r);
}
}tmp,A,B,C;
node check(int i,int j){
if(i>=j||i<1||str[1]=='0'&&i>1||str[i+1]=='0'&&j>i+1)return tmp;
A.solve(1,i);
B.solve(i+1,j);
A+=B;
return A;
}
void solve(){
tmp.a=2e9;
tmp.b=2e9;
for(int i=n;i>=1;i--){
if(str[i]=='0'&&i!=n)continue;
C.solve(i,n);
int len=n-i+1;
if(check(len,i-1)==C){
ansa=len;
ansb=i-1;
return;
}
if(check(len-1,i-1)==C){
ansa=len-1;
ansb=i-1;
return;
}
if(check(i-1-len,i-1)==C){
ansa=i-1-len;
ansb=i-1;
return;
}
if(check(i-len,i-1)==C){
ansa=i-len;
ansb=i-1;
return;
}
}
}
int main(){
scanf("%s",str+1);
n=strlen(str+1);
hash1.init(10,1e9+13);
hash2.init(10,1e9+9);
solve();
for(int i=1;i<=n;i++){
printf("%c",str[i]);
if(ansa==i)putchar('+');
else if(ansb==i)putchar('=');
}
return 0;
}
```
--------------
[例题 专题C](https://cn.vjudge.net/contest/277011#problem/C)
**题意**：输入矩阵$A$，矩阵$B$，问矩阵$B$ 在 矩阵$A$ 中出现了多少次。
**思路**：最重要的是怎么把一个矩阵$hash$成一个值，每一个字符对应的系数应该是多少，然后怎么相减减出来。
可以造一个矩阵来说明：
$$\begin{bmatrix} 1&2&3 \\ 4&5&6\\7&8&9 \end{bmatrix}$$
数字表示对应位置的系数。
**做法**：先预处理横着的$sum$ 的 $hash$ 前缀，然后按列处理即可。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e3+5;
int ans;
long long tot;
struct Matrix{
int n,m;
char mp[maxn][maxn];
struct Hash{
int tot,sum[maxn][maxn],f[maxn],base,P;
void init(int Bas,int Pi,char mp[maxn][maxn],int n,int m){
P=Pi;base=Bas;
tot=0;
f[0]=1;
for(int i=1;i<maxn;i++)
f[i]=1LL*f[i-1]*base%P;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
sum[i][j]=(1LL*sum[i][j-1]*base+mp[i][j]-'a')%P;
tot=(1LL*tot*f[m]+sum[i][m])%P;
}
}
int solve(int row,int l,int r){
return (sum[row][r]-1LL*sum[row][l-1]*f[r-l+1]%P+P)%P;
}
}hash1,hash2;
struct node{
int len,sum1[maxn],sum2[maxn],f1[maxn],f2[maxn];
void init(int l,int r,int n,int h1[maxn],int h2[maxn],int Sum1[maxn][maxn],int Sum2[maxn][maxn],int P1,int P2){
len=r-l+1;
f1[0]=f2[0]=1;
for(int i=1;i<=n;i++){
f1[i]=1LL*f1[i-1]*h1[len]%P1;
f2[i]=1LL*f2[i-1]*h2[len]%P2;
}
#define solve1(row,l,r) (Sum1[row][r]-1LL*Sum1[row][l-1]*h1[r-l+1]%P1+P1)%P1
#define solve2(row,l,r) (Sum2[row][r]-1LL*Sum2[row][l-1]*h2[r-l+1]%P2+P2)%P2
for(int i=1;i<=n;i++){
// debug(solve1(i,l,r));
sum1[i]=(1LL*sum1[i-1]*h1[len]+solve1(i,l,r))%P1;
sum2[i]=(1LL*sum2[i-1]*h2[len]+solve2(i,l,r))%P2;
}
}
long long solve(int l,int r,int P1,int P2){
int a=(sum1[r]-1LL*sum1[l-1]*f1[r-l+1]%P1+P1)%P1;
int b=(sum2[r]-1LL*sum2[l-1]*f2[r-l+1]%P2+P2)%P2;
return a|b<<32;
}
}S;
void read(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
hash1.init(29,1e9+7,mp,n,m);
hash2.init(31,1e9+9,mp,n,m);
tot=hash1.tot|hash2.tot<<32;
}
void check(int x,int l,int r){
S.init(l,r,n,hash1.f,hash2.f,hash1.sum,hash2.sum,hash1.P,hash2.P);
for(int i=1;i<=n-x+1;i++){
if(S.solve(i,i+x-1,hash1.P,hash2.P)==tot){
ans++;
}
}
}
}A,B;
int main(){
for(int _=(cin>>_,_);_--;){
ans=0;
A.read();B.read();
for(int i=1;i<=A.m-B.m+1;i++){
A.check(B.n,i,i+B.m-1);
}
printf("%d\n",ans);
}
return 0;
}
```
>如果你认真看完了上面的代码，你会发现它其丑无比。
>原因就是我希望弄一个双$hash$，然而一个结构体里面的两个结构体不能调用函数，所以。。。
>就表现出一直在引用数组的尴尬情况。
### 划重点：hash被卡的概率是比较低的，如果不是离线赛可以用单hash，如果错了，尝试改$P$的值就行了
-----------
> _这是后来加的_：hash的时候一定要$+1$！！，不然的话很容易冲突，比如说 $a$ 和 $aaa$ ，（如果不$+1$）他们都是0