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.↵
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.↵
