Content

Friday, January 1, 2021

Hashing

Source :

Link1 Link2 Link3

Code :

#include<bits/stdc++.h>
using namespace std;
#define MAX 2000005
#define ll long long
///Hash function: hash(i+1) = (i = 0 to n-1) ((hash(i) * base) + s[i]) mod m
///Hash of a substring: hash(s[i...j]) = (hash(s[0...j]) - (hash(s[0...i-1]) * pow[j-i+1]) + m) mod m
const ll p1 = 737;
const ll p2 = 3079;
const ll m1 = 1e9+7; // 1000000123
const ll m2 = 1e9+9; // 1000000321
vector<ll>p_pow1(MAX), p_pow2(MAX), h1(MAX, 0), h2(MAX, 0);
void Hash(string const& s)
{
int n = s.size();
p_pow1[0] = 1;
p_pow2[0] = 1;
for(int i = 1; i < n; i++)
{
p_pow1[i] = (p_pow1[i-1] * p1) % m1;
p_pow2[i] = (p_pow2[i-1] * p2) % m2;
}
for(int i = 0; i < n; i++)
{
h1[i+1] = ((h1[i] * p1) % m1 + (s[i] - 'a' + 1)) % m1;
h2[i+1] = ((h2[i] * p2) % m2 + (s[i] - 'a' + 1)) % m2;
}
}
ll get_Hash(int l, int r)
{
ll val = (h1[r] - (h1[l-1] * p_pow1[r-l+1]) % m1 + m1) % m1;
return val;
}
int main()
{
string s;
cin>>s;
Hash(s);
int l, r;
cin>>l>>r;
cout<<get_Hash(l, r)<<endl;
return 0;
}
view raw hashing.cpp hosted with ❤ by GitHub

Application :

1. Given a text and a pattern. Find all occurrences of the pattern.

:: Check all sub-strings of length |pattern| in text & compare hash value in O(|text| + |pattern|).

2. Given two string S1 & S2. Find longest common sub-string between them.

:: Binary search on length and check them with Hash value.

3. Find lexicographic minimal cyclic shift of a string of length n.

:: See this.

4. Given a string S. Find a smallest period in it.

 :: Let answer will be of length X and it will divide |S|. Then we will check Hash value of S[0...n-x-1] & S[x...n-1] are equal or not.

5. Given two trees. Check if they are isomorphic or not.

:: Read this.

6. Read this also.

Problem :

1. NHAY - A Needle in the Haystack

2. ADAPHOTO - Ada and Terramorphing (10^6 version)

3. 1517. Freedom of Choice (10^5 version)

4. Minimal Rotation

5.  C. Watto and Mechanism

6. D. Palindrome pairs

7. E. Games on a CD

*** Solve all problems mentioned in CP algo.

No comments:

Post a Comment