Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

How to effectively Hash the String for Rabin-Karp?

Правка en1, от codeDominus, 2018-04-04 22:25:00

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.

Thanks in Advance.

Теги rabin-karp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский codeDominus 2018-04-04 22:25:00 627 Initial revision (published)