Please read the new rule regarding the restriction on the use of AI tools. ×

String Hash
Difference between en1 and en2, changed 180 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English harrypang 2024-07-21 06:28:42 17 Tiny change: 'odeforces.\n' -> 'odeforces.____from cwz2024.\n'
en2 English harrypang 2024-07-21 06:27:42 180
en1 English harrypang 2024-07-20 16:45:41 1267 Initial revision (published)