String hash,encrypted strings embody strings as concrete numbers.
ordinary
const int Mod=998244353; //1e9+7 also commonly used modulus.
const int base=131; //13331 also commonly used base (i.e., seed) .
LL has[N],pw[N]; //The values of the hash and the power of the base
void init_hash(){
pw[0]=1;
for(int i=1;i<N;i++){
pw[i]=pw[i-1]*base%Mod;
}
}
void make_hash(string s){ //Generate a hash for string s.
has[0]=s[0]%Mod;
for(int i=1;i<s.size();i++){
has[i]=(has[i-1]*base%Mod+s[i]%Mod)%Mod;
}
}
int get_hash(int l,int r){ //Find the hash value of the string l~r.
return (has[r]-has[l-1]*pw[r-l+1]%Mod+Mod)%Mod;
}
double hash
To open a double hash, simply open two structures and assign different moduli.
struct Hash{
int Mod,base,has[N],pw[N];
void init(int Mod_in,int base_in){
Mod=Mod_in,base=base_in;
pw[0]=1;
for(int i=1;i<N;i++){
pw[i]=pw[i-1]*base%Mod;
}
}
void make(string s){
has[0]=s[0]%Mod;
for(int i=1;i<s.size();i++){
has[i]=(has[i-1]*base%Mod+s[i])%Mod;
}
}
int get(int l,int r){
return (has[r]-has[l-1]*pw[r-l+1]%Mod+Mod)%Mod;
}
}; //Works better in struct