我们经常会遇到需要比较字符串大小的情况，普通的方法是使用一个for循环来进行比较，这样时间复杂度是\(O(n)\)的，非常慢
但是相比较之下数字比较就很快，那我们可以把字符串转换为数字进行比较
所以进入正题
进制Hash
有一个字符串abc
我们知道每一个字符使用ASCII码存储的
我们还知道一种东西叫做进制
我们可以把一个字符串看作是一个B进制的数
那么，我们把这个“数”转十进制会得到一个值，我们叫做Hash值
伪代码：
for(int i=1;i<=len;i++){ans+=s[i]*power;power*=B;
}
但这样还是要跑O(n)啊
我们可以考虑预处理，类似O(n)预处理，O(1)查询的模式
预处理:
power[0]=1;
for(int i=1;i<=len;i++){power[i]=power[i-1]*B;
}
for(int i=1;i<=len;i++){val[i]=val[i-1]*B+s[i];
}
那么我们进一步发现，可以·得到一个区间的Hash值：
int get_hash(int l,int r){return val[r]-val[l-1]*pw[r-l+1];
}
分析过程到时候补上
P3370
这里我们为了避免哈希冲突，可以考虑双哈希
如果两个哈希值都有过的话大概就是已经出现过了，其他情况就是没出现过
#include<bits/stdc++.h>
#define int unsigned long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18,B=13331,b=13131;
int n;
int t1[maxn],t2[maxn];
int get_hash1(string s){int res=1;int sum=0;for(int i=0;i<s.size();i++){sum+=s[i]*res;res*=B;}return sum;
}
int get_hash2(string s){int res=1;int sum=0;for(int i=0;i<s.size();i++){sum+=s[i]*res;res*=b;}return sum;
}
signed main(){cin>>n;int ans=0;for(int i=1;i<=n;i++){string s;cin>>s;int x=get_hash1(s);int y=get_hash2(s);if(t1[x]&&t2[y]){continue;}ans++;t1[x]++;t2[y]++;}cout<<ans<<endl;return 0;
}
P10468
区间Hash值模板题
#include<bits/stdc++.h>
#define int unsigned long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18,B=13131;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
string s;
int val[maxn],pw[maxn];
int get_hash(int l,int r){return val[r]-val[l-1]*pw[r-l+1];
}
signed main(){cin>>s;int len=s.size();s='#'+s;pw[0]=1;for(int i=1;i<=len;i++){val[i]=val[i-1]*B+s[i];pw[i]=pw[i-1]*B;}int q;cin>>q;while(q--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(get_hash(l1,r1)==get_hash(l2,r2)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;
}