### codeDominus's blog

By codeDominus, history, 6 years ago,

I am trying to solve this problem using rabin-karp maching algorithm.

My hash function is

ll hash = 0;
ll P = 3; // only 3 characters are considered here 'a' ,'b', 'c';
ll MOD = 1e9+7;
string s; // hash of this string is calculated
for(int i=0; i<s.size();i++)
{
hash = (hash + (pow(P,i)*(s[i]-'a'+1))%MOD)%MOD;
}


Is there any better way to calculate the hash function to avoid conflict?

I tried to change (s[i] — 'a' + 1) by s[i]. Still getting conflict.

 » 6 years ago, # |   +4 You most likely encountered the Birthday Paradox.To fix this, either maintain two hashes with different P and MOD, or calculate one hash with a large enough MOD (watch out for overflow!).
 » 5 weeks ago, # |   0 #include #define ll long long int using namespace std; ll MOD1 = 1e9+7; ll MOD2 = 1e9+7; ll prime1 = 54059; ll prime2 = 257; void solve() { vector p1(1e6, 1), p2(1e6, 1); for(int i=1; i<=7e5; i++) { p1[i] = (p1[i-1]*prime1) % MOD1; p2[i] = (p2[i-1]*prime2) % MOD2; } int n, m; cin >> n >> m; map mpp1; map mpp2; while(n--) { string s; cin >> s; int l = s.length(); ll hash1 = 0; ll hash2 = 0; for(int i=0; i> s; int l = s.length(); ll hash1 = 0; ll hash2 = 0; for(int i=0; i