### 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.

• +5

By codeDominus, history, 7 years ago,

I solved the problem using DSU; My logic: let suppose there is two disjoint set of size M and N where each member is a friend of every other in the set. now suppose one member of 1st set become friend of a member of 2nd set. we need total of m*n such friendship for every member of 1st set to become friends with every other member of 2nd set.

is there any mistake in my logic ?(posting me solution just for logic not for debugging)

my solution