### In the name of Allah↵
### --------------------↵
Hello my friends ! I have a prize for you, Actually I always have a problem with KMP. So I try to use hash string instead. I think it wood be great if we have a struct like hash and can easily work with it. So I make it !↵
here I implemented hash struct with C++ & you can have fun with it.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
template <typename X, typename Y, typename Z>↵
long long int Pow(const X &a, const Y &b, const Z &mod) /// # O(log(b))↵
{↵
if(b == 0) return 1LL;↵
long long int x = Pow(a,b/2,mod);↵
return b%2 == 0? x*x%mod : (long long int)a * (x * x % mod) % mod;↵
}↵
↵
bool ready = false;↵
const long long int MAX_Hash = 1e6 + 5;↵
const long long int mod1 = 1e9 + 7;↵
const long long int mod2 = 1e9 + 9;↵
const long long int C = 257LL;↵
long long int C1[MAX_Hash];↵
long long int C2[MAX_Hash];↵
long long int pow1[MAX_Hash];↵
long long int pow2[MAX_Hash];↵
↵
void fill_C()↵
{↵
C1[0] = C2[0] = 1LL;↵
for(int i = 1; i < MAX_Hash; i++)↵
{↵
C1[i] = (C1[i-1] * C) % mod1;↵
C2[i] = (C2[i-1] * C) % mod2;↵
}↵
}↵
↵
void fill_pow()↵
{↵
pow1[0] = pow2[0] = 1LL;↵
pow1[1] = Pow(C,mod1-2,mod1);↵
pow2[1] = Pow(C,mod2-2,mod2);↵
for(int i = 2; i < MAX_Hash; i++)↵
{↵
pow1[i] = pow1[i-1] * pow1[1] % mod1;↵
pow2[i] = pow2[i-1] * pow2[1] % mod2;↵
}↵
}↵
↵
void GetReady()↵
{↵
ready = true;↵
fill_C();↵
fill_pow();↵
}↵
↵
struct Hash↵
{↵
long long int val1 = 0, val2 = 0, S = 0;↵
↵
Hash() /// # O(1)↵
{↵
if(!ready)GetReady();↵
}↵
↵
Hash(const char &x) /// # O(1)↵
{↵
Hash();↵
push_back(x);↵
}↵
↵
Hash(char *s, const char *e) /// # O(Len)↵
{↵
Hash();↵
push_back(s,e);↵
}↵
↵
Hash(const string &s) /// # O(len)↵
{↵
Hash();↵
push_back(s);↵
}↵
↵
Hash(const Hash &A) /// # O(1)↵
{↵
Hash();↵
push_back(A);↵
}↵
↵
void clear() /// # O(1)↵
{↵
S = val1 = val2 = 0LL;↵
}↵
↵
void push_back(const char &x) /// # O(1)↵
{↵
S++;↵
val1 *= C1[1];↵
val1 += (long long int)x;↵
val1 %= mod1;↵
val2 *= C2[1];↵
val2 += (long long int)x;↵
val2 %= mod2;↵
}↵
↵
void push_back(const string &s) /// # O(len)↵
{↵
for(auto u: s)↵
push_back(u);↵
}↵
↵
void push_back(char *s, const char *e) /// # O(len)↵
{↵
while(s != e)↵
{↵
push_back(*s);↵
s++;↵
}↵
}↵
↵
void push_back(const Hash &A) /// # O(1)↵
{↵
val1 *= C1[A.S];↵
val1 += A.val1;↵
val1 %= mod1;↵
val2 *= C2[A.S];↵
val2 += A.val2;↵
val2 %= mod2;↵
S += A.S;↵
}↵
↵
void push_front(const char &x) /// # O(1)↵
{↵
val1 += (long long int)x * C1[S];↵
val1 %= mod1;↵
val2 += (long long int)x * C2[S];↵
val2 %= mod2;↵
S++;↵
}↵
↵
void push_front(const string &s) /// # O(len)↵
{↵
for(int i = s.size()-1; i >= 0; i--)↵
push_front(s[i]);↵
}↵
↵
void push_front(const char *s, char *e) /// # O(len)↵
{↵
if(e == s)return;↵
do↵
{↵
e--;↵
push_back(*e);↵
}while(s != e);↵
}↵
↵
void push_front(const Hash &A) /// # O(1)↵
{↵
val1 += A.val1 * C1[S];↵
val1 %= mod1;↵
val2 += A.val2 * C2[S];↵
val2 %= mod2;↵
S += A.S;↵
}↵
↵
void operator+=(const Hash &A) /// # O(1)↵
{↵
push_back(A);↵
}↵
↵
void operator+=(const char &x) /// # O(1)↵
{↵
push_back(x);↵
}↵
↵
void operator+=(const string &s) /// # O(len)↵
{↵
push_back(s);↵
}↵
↵
void pop_back(const char &x) /// # O(1)↵
{↵
S--;↵
val1 -= (long long int)x;↵
val1 *= pow1[1];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= (long long int)x;↵
val2 *= pow2[1];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_back(const string &s) /// # O(len)↵
{↵
for(int i = s.size()-1; i >= 0; i--)↵
pop_back(s[i]);↵
}↵
↵
void pop_back(const char *s, char *e) /// # O(len)↵
{↵
if(e == s)return;↵
do↵
{↵
e--;↵
pop_back(*e);↵
}while(s != e);↵
}↵
↵
void pop_back(const Hash &A) /// # O(1)↵
{↵
S -= A.S;↵
val1 -= A.val1;↵
val1 *= pow1[A.S];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= A.val2;↵
val2 *= pow2[A.S];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_front(const char &x) /// # O(1)↵
{↵
S--;↵
val1 -= (long long int)x * C1[S];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= (long long int)x * C2[S];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_front(const string &s) /// # O(len)↵
{↵
for(auto u: s)↵
pop_front(u);↵
}↵
↵
void pop_front(char *s, const char *e) /// # O(len)↵
{↵
while(s!=e)↵
{↵
pop_front(*s);↵
s++;↵
}↵
}↵
↵
void pop_front(const Hash &A) /// # O(1)↵
{↵
S -= A.S;↵
val1 -= A.val1 * C1[S];↵
val1 = (val1%mod1+mod1)%mod1;↵
val2 -= A.val2 * C2[S];↵
val2 = (val2%mod2+mod2)%mod2;↵
}↵
↵
void operator-=(const Hash &A) /// # O(1)↵
{↵
pop_back(A);↵
}↵
↵
void operator-=(const char &x) /// # O(1)↵
{↵
pop_back(x);↵
}↵
↵
void operator-=(const string &s) /// # O(len)↵
{↵
pop_back(s);↵
}↵
↵
void operator=(const char &s) /// # O(1)↵
{↵
val1 = (long long int)s;↵
val2 = (long long int)s;↵
S = 1LL;↵
}↵
↵
void operator=(const string &s) /// # O(len)↵
{↵
clear();↵
push_back(s);↵
}↵
↵
void operator=(const Hash &A) /// # O(1)↵
{↵
val1 = A.val1;↵
val2 = A.val2;↵
S = A.S;↵
}↵
↵
bool operator==(const Hash &A) const /// # O(1)↵
{↵
return (val1 == A.val1 && val2 == A.val2 && S == A.S);↵
}↵
↵
bool operator==(const string &s) const /// # O(len)↵
{↵
Hash A(s);↵
return (val1 == A.val1 && val2 == A.val2 && S == A.S);↵
}↵
↵
bool operator==(const char &x) const /// # O(1)↵
{↵
return (val1 == (long long int)x && val2 == (long long int)x && S == 1);↵
}↵
↵
bool empty() /// # O(1)↵
{↵
return (S == 0);↵
}↵
↵
long long int size() /// # O(1)↵
{↵
return S;↵
}↵
}EMPTY, PLUS, MINUS;↵
↵
template <typename T>↵
Hash operator+(const Hash &A, const T &B)↵
{↵
PLUS = A;↵
PLUS += B;↵
return PLUS;↵
}↵
↵
template <typename T>↵
Hash operator-(const Hash &A, const T &B)↵
{↵
MINUS = A;↵
MINUS -= B;↵
return MINUS;↵
}↵
int main()↵
{↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
you can push_back, pop_back, push_front, pop_front a char*, string ,a char and also a hash to your hash and many other work. notice mainly when you want to use a string or a char* program handle on O(length) but when you use hash or a char it will be O(1). and also for the first time you want to hash some thing program does Preprocessing in O(MAX_Hash) where MAX_Hash is max length of a string you want to hash it, you can easily set it. its default is 1e6 + 5.↵
↵
For the theory part you can visit :↵
https://cp-algorithms.com/string/string-hashing.html↵
↵
about variable I use:↵
`S is length of hashed string`, `val1 is hash of string in mod mod1`, `val2 is hash of string in mod mod2`.↵
note : there is no Anti-hash yet that can hack you with this hash function.↵
↵
Now I want to introduce functions one by one in examples:↵
↵
~~~~~↵
char t[20] = "Hash Struct . . .";↵
string s = "OK!";↵
Hash A; /// simple↵
Hash B("Hello codeforces !"); /// give a string↵
Hash C(t,t+17); /// give a char* with two pointers↵
Hash D(B); /// give an other Hash↵
↵
B.clear(); /// now B is completely empty↵
↵
D.push_back('@'); /// -@- will added to end of D↵
B.push_back(s); /// string s will added to end of B↵
B.push_back(t,t+4); /// -Hash- (t,t+4) will added to end of B↵
C.push_back(A); /// A will added to C but A was empty and has no effect↵
↵
D.push_front('_'); /// -_ will added to front of D↵
B.push_front("String B is :"); /// -String B is :- will added to front of B↵
A.push_front(t+5,t+12); /// -Struct - (t+5,t+12) will added to front of A↵
C.push_front(A); /// A will added to front of C↵
↵
B += D; /// D will added to end of B↵
A += '%'; /// -%- will added to end of A↵
C += "I am C !"; /// -I am C !- will added to end of C↵
↵
/*↵
notice pop_back and pop_front should give a real char, string, char* or a Hash↵
for example A is "Struct" now and we can:↵
*/↵
A.pop_back('t'); /// -Struct- -> -Struc-↵
A.pop_back("uc"); /// -Struc- -> -Str-↵
A.pop_back(t+7,t+8); /// -Str- -> -St-↵
A.pop_back(A); /// It's unusual way to clear a Hash !↵
↵
/// B's front is -String B is :-↵
B.pop_front("String"); /// -String B is :- -> - B is :-↵
B.pop_front(' '); /// - B is :- -> -B is :-↵
B.pop_front(t+4,t+4); /// nothing↵
B.pop_front(B); /// It's unusual way to clear a Hash !↵
↵
/// -= is like pop_back so now C has -I am C !- at end↵
C -= '!'; /// -I am C !- -> -I am C -↵
C -= " C "; /// -I am C - -> -I am-↵
C -= C; /// C now is empty but if for example Hash E = " am", you can write C -= E => -I am- -> -I-↵
↵
D = '*'; /// now D is just -*-↵
A = "ABCD"; /// now A is just -ABCD-↵
B = A; /// now B is just like A means -ABCD- here↵
↵
A == B; /// return true if A is_equal to B else false↵
D == "ABDE"; /// return true if A is_equal to -ABDE- else false↵
D == '*'; /// return true if D = -*- else false↵
↵
C.empty(); /// return true if and just if length of C is 0↵
C.size(); /// return length of C↵
↵
D = A + B - C; /// D will be A + B - C(it's different from A - C + B)↵
~~~~~↵
↵
At last If you have a suggestion or want to know something or find a bug(you can't find bug but maybe) or else please and please tell me by writing comments.↵
↵
Hope to enjoy it.↵
↵
THE END . . .
### --------------------↵
Hello my friends ! I have a prize for you, Actually I always have a problem with KMP. So I try to use hash string instead. I think it wood be great if we have a struct like hash and can easily work with it. So I make it !↵
here I implemented hash struct with C++ & you can have fun with it.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
template <typename X, typename Y, typename Z>↵
long long int Pow(const X &a, const Y &b, const Z &mod) /// # O(log(b))↵
{↵
if(b == 0) return 1LL;↵
long long int x = Pow(a,b/2,mod);↵
return b%2 == 0? x*x%mod : (long long int)a * (x * x % mod) % mod;↵
}↵
↵
bool ready = false;↵
const long long int MAX_Hash = 1e6 + 5;↵
const long long int mod1 = 1e9 + 7;↵
const long long int mod2 = 1e9 + 9;↵
const long long int C = 257LL;↵
long long int C1[MAX_Hash];↵
long long int C2[MAX_Hash];↵
long long int pow1[MAX_Hash];↵
long long int pow2[MAX_Hash];↵
↵
void fill_C()↵
{↵
C1[0] = C2[0] = 1LL;↵
for(int i = 1; i < MAX_Hash; i++)↵
{↵
C1[i] = (C1[i-1] * C) % mod1;↵
C2[i] = (C2[i-1] * C) % mod2;↵
}↵
}↵
↵
void fill_pow()↵
{↵
pow1[0] = pow2[0] = 1LL;↵
pow1[1] = Pow(C,mod1-2,mod1);↵
pow2[1] = Pow(C,mod2-2,mod2);↵
for(int i = 2; i < MAX_Hash; i++)↵
{↵
pow1[i] = pow1[i-1] * pow1[1] % mod1;↵
pow2[i] = pow2[i-1] * pow2[1] % mod2;↵
}↵
}↵
↵
void GetReady()↵
{↵
ready = true;↵
fill_C();↵
fill_pow();↵
}↵
↵
struct Hash↵
{↵
long long int val1 = 0, val2 = 0, S = 0;↵
↵
Hash() /// # O(1)↵
{↵
if(!ready)GetReady();↵
}↵
↵
Hash(const char &x) /// # O(1)↵
{↵
Hash();↵
push_back(x);↵
}↵
↵
Hash(char *s, const char *e) /// # O(Len)↵
{↵
Hash();↵
push_back(s,e);↵
}↵
↵
Hash(const string &s) /// # O(len)↵
{↵
Hash();↵
push_back(s);↵
}↵
↵
Hash(const Hash &A) /// # O(1)↵
{↵
Hash();↵
push_back(A);↵
}↵
↵
void clear() /// # O(1)↵
{↵
S = val1 = val2 = 0LL;↵
}↵
↵
void push_back(const char &x) /// # O(1)↵
{↵
S++;↵
val1 *= C1[1];↵
val1 += (long long int)x;↵
val1 %= mod1;↵
val2 *= C2[1];↵
val2 += (long long int)x;↵
val2 %= mod2;↵
}↵
↵
void push_back(const string &s) /// # O(len)↵
{↵
for(auto u: s)↵
push_back(u);↵
}↵
↵
void push_back(char *s, const char *e) /// # O(len)↵
{↵
while(s != e)↵
{↵
push_back(*s);↵
s++;↵
}↵
}↵
↵
void push_back(const Hash &A) /// # O(1)↵
{↵
val1 *= C1[A.S];↵
val1 += A.val1;↵
val1 %= mod1;↵
val2 *= C2[A.S];↵
val2 += A.val2;↵
val2 %= mod2;↵
S += A.S;↵
}↵
↵
void push_front(const char &x) /// # O(1)↵
{↵
val1 += (long long int)x * C1[S];↵
val1 %= mod1;↵
val2 += (long long int)x * C2[S];↵
val2 %= mod2;↵
S++;↵
}↵
↵
void push_front(const string &s) /// # O(len)↵
{↵
for(int i = s.size()-1; i >= 0; i--)↵
push_front(s[i]);↵
}↵
↵
void push_front(const char *s, char *e) /// # O(len)↵
{↵
if(e == s)return;↵
do↵
{↵
e--;↵
push_back(*e);↵
}while(s != e);↵
}↵
↵
void push_front(const Hash &A) /// # O(1)↵
{↵
val1 += A.val1 * C1[S];↵
val1 %= mod1;↵
val2 += A.val2 * C2[S];↵
val2 %= mod2;↵
S += A.S;↵
}↵
↵
void operator+=(const Hash &A) /// # O(1)↵
{↵
push_back(A);↵
}↵
↵
void operator+=(const char &x) /// # O(1)↵
{↵
push_back(x);↵
}↵
↵
void operator+=(const string &s) /// # O(len)↵
{↵
push_back(s);↵
}↵
↵
void pop_back(const char &x) /// # O(1)↵
{↵
S--;↵
val1 -= (long long int)x;↵
val1 *= pow1[1];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= (long long int)x;↵
val2 *= pow2[1];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_back(const string &s) /// # O(len)↵
{↵
for(int i = s.size()-1; i >= 0; i--)↵
pop_back(s[i]);↵
}↵
↵
void pop_back(const char *s, char *e) /// # O(len)↵
{↵
if(e == s)return;↵
do↵
{↵
e--;↵
pop_back(*e);↵
}while(s != e);↵
}↵
↵
void pop_back(const Hash &A) /// # O(1)↵
{↵
S -= A.S;↵
val1 -= A.val1;↵
val1 *= pow1[A.S];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= A.val2;↵
val2 *= pow2[A.S];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_front(const char &x) /// # O(1)↵
{↵
S--;↵
val1 -= (long long int)x * C1[S];↵
val1 = ((val1%mod1)+mod1)%mod1;↵
val2 -= (long long int)x * C2[S];↵
val2 = ((val2%mod2)+mod2)%mod2;↵
}↵
↵
void pop_front(const string &s) /// # O(len)↵
{↵
for(auto u: s)↵
pop_front(u);↵
}↵
↵
void pop_front(char *s, const char *e) /// # O(len)↵
{↵
while(s!=e)↵
{↵
pop_front(*s);↵
s++;↵
}↵
}↵
↵
void pop_front(const Hash &A) /// # O(1)↵
{↵
S -= A.S;↵
val1 -= A.val1 * C1[S];↵
val1 = (val1%mod1+mod1)%mod1;↵
val2 -= A.val2 * C2[S];↵
val2 = (val2%mod2+mod2)%mod2;↵
}↵
↵
void operator-=(const Hash &A) /// # O(1)↵
{↵
pop_back(A);↵
}↵
↵
void operator-=(const char &x) /// # O(1)↵
{↵
pop_back(x);↵
}↵
↵
void operator-=(const string &s) /// # O(len)↵
{↵
pop_back(s);↵
}↵
↵
void operator=(const char &s) /// # O(1)↵
{↵
val1 = (long long int)s;↵
val2 = (long long int)s;↵
S = 1LL;↵
}↵
↵
void operator=(const string &s) /// # O(len)↵
{↵
clear();↵
push_back(s);↵
}↵
↵
void operator=(const Hash &A) /// # O(1)↵
{↵
val1 = A.val1;↵
val2 = A.val2;↵
S = A.S;↵
}↵
↵
bool operator==(const Hash &A) const /// # O(1)↵
{↵
return (val1 == A.val1 && val2 == A.val2 && S == A.S);↵
}↵
↵
bool operator==(const string &s) const /// # O(len)↵
{↵
Hash A(s);↵
return (val1 == A.val1 && val2 == A.val2 && S == A.S);↵
}↵
↵
bool operator==(const char &x) const /// # O(1)↵
{↵
return (val1 == (long long int)x && val2 == (long long int)x && S == 1);↵
}↵
↵
bool empty() /// # O(1)↵
{↵
return (S == 0);↵
}↵
↵
long long int size() /// # O(1)↵
{↵
return S;↵
}↵
}EMPTY, PLUS, MINUS;↵
↵
template <typename T>↵
Hash operator+(const Hash &A, const T &B)↵
{↵
PLUS = A;↵
PLUS += B;↵
return PLUS;↵
}↵
↵
template <typename T>↵
Hash operator-(const Hash &A, const T &B)↵
{↵
MINUS = A;↵
MINUS -= B;↵
return MINUS;↵
}↵
int main()↵
{↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
you can push_back, pop_back, push_front, pop_front a char*, string ,a char and also a hash to your hash and many other work. notice mainly when you want to use a string or a char* program handle on O(length) but when you use hash or a char it will be O(1). and also for the first time you want to hash some thing program does Preprocessing in O(MAX_Hash) where MAX_Hash is max length of a string you want to hash it, you can easily set it. its default is 1e6 + 5.↵
↵
For the theory part you can visit :↵
https://cp-algorithms.com/string/string-hashing.html↵
↵
about variable I use:↵
`S is length of hashed string`, `val1 is hash of string in mod mod1`, `val2 is hash of string in mod mod2`.↵
note : there is no Anti-hash yet that can hack you with this hash function.↵
↵
Now I want to introduce functions one by one in examples:↵
↵
~~~~~↵
char t[20] = "Hash Struct . . .";↵
string s = "OK!";↵
Hash A; /// simple↵
Hash B("Hello codeforces !"); /// give a string↵
Hash C(t,t+17); /// give a char* with two pointers↵
Hash D(B); /// give an other Hash↵
↵
B.clear(); /// now B is completely empty↵
↵
D.push_back('@'); /// -@- will added to end of D↵
B.push_back(s); /// string s will added to end of B↵
B.push_back(t,t+4); /// -Hash- (t,t+4) will added to end of B↵
C.push_back(A); /// A will added to C but A was empty and has no effect↵
↵
D.push_front('_'); /// -_ will added to front of D↵
B.push_front("String B is :"); /// -String B is :- will added to front of B↵
A.push_front(t+5,t+12); /// -Struct - (t+5,t+12) will added to front of A↵
C.push_front(A); /// A will added to front of C↵
↵
B += D; /// D will added to end of B↵
A += '%'; /// -%- will added to end of A↵
C += "I am C !"; /// -I am C !- will added to end of C↵
↵
/*↵
notice pop_back and pop_front should give a real char, string, char* or a Hash↵
for example A is "Struct" now and we can:↵
*/↵
A.pop_back('t'); /// -Struct- -> -Struc-↵
A.pop_back("uc"); /// -Struc- -> -Str-↵
A.pop_back(t+7,t+8); /// -Str- -> -St-↵
A.pop_back(A); /// It's unusual way to clear a Hash !↵
↵
/// B's front is -String B is :-↵
B.pop_front("String"); /// -String B is :- -> - B is :-↵
B.pop_front(' '); /// - B is :- -> -B is :-↵
B.pop_front(t+4,t+4); /// nothing↵
B.pop_front(B); /// It's unusual way to clear a Hash !↵
↵
/// -= is like pop_back so now C has -I am C !- at end↵
C -= '!'; /// -I am C !- -> -I am C -↵
C -= " C "; /// -I am C - -> -I am-↵
C -= C; /// C now is empty but if for example Hash E = " am", you can write C -= E => -I am- -> -I-↵
↵
D = '*'; /// now D is just -*-↵
A = "ABCD"; /// now A is just -ABCD-↵
B = A; /// now B is just like A means -ABCD- here↵
↵
A == B; /// return true if A is_equal to B else false↵
D == "ABDE"; /// return true if A is_equal to -ABDE- else false↵
D == '*'; /// return true if D = -*- else false↵
↵
C.empty(); /// return true if and just if length of C is 0↵
C.size(); /// return length of C↵
↵
D = A + B - C; /// D will be A + B - C(it's different from A - C + B)↵
~~~~~↵
↵
At last If you have a suggestion or want to know something or find a bug(you can't find bug but maybe) or else please and please tell me by writing comments.↵
↵
Hope to enjoy it.↵
↵
THE END . . .
