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.