harrypang's blog

By harrypang, history, 4 months ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your guidance, I'm a beginner and I want to save the template in my blog.^_^

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by harrypang (previous revision, new revision, compare).