Struct of Hash String
Разница между en2 и en3, 5 символ(ов) изменены
### 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 . . .

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский MohammadParsaElahimanesh 2021-03-17 11:32:23 5 Tiny change: 'ue if and if length' -> 'ue if and just if length'
en2 Английский MohammadParsaElahimanesh 2021-02-06 16:09:15 0 (published)
en1 Английский MohammadParsaElahimanesh 2021-02-06 16:08:18 10378 Initial revision (saved to drafts)