String Hash

Revision en1, by harrypang, 2024-07-20 16:45:41

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
Tags hash

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)