Source :
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; | |
} |
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)
*** Solve all problems mentioned in CP algo.
No comments:
Post a Comment