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 . . .
