Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. Оно применяется начиная с раунда 972. ×

Блог пользователя harrypang

Автор harrypang, история, 2 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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