String Hash

Правка en3, от harrypang, 2024-07-21 06:28:42

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.

Теги hash

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский harrypang 2024-07-21 06:28:42 17 Tiny change: 'odeforces.\n' -> 'odeforces.____from cwz2024.\n'
en2 Английский harrypang 2024-07-21 06:27:42 180
en1 Английский harrypang 2024-07-20 16:45:41 1267 Initial revision (published)