### harrypang's blog

By harrypang, history, 2 weeks ago,

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


But at least using chrono::steady_clock::now().time_since_epoch().count() and mt_19937 to generate random bases otherwise your hashing solution will be easily hacked in codeforces.____from cwz2024.

• +2

 » 2 weeks ago, # |   +3 Well, all the hashes in the post are weak hashes, including the double hash. At least using chrono::steady_clock::now().time_since_epoch().count() and mt_19937 to generate random bases otherwise your hashing solution will be easily hacked in codeforces.
•  » » 2 weeks ago, # ^ |   0 Thank you for your guidance, I'm a beginner and I want to save the template in my blog.^_^
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by harrypang (previous revision, new revision, compare).