Rabin Karp Algorithm

help
,
1

In this Rabin Karp Algorithm implementation cp-algorithms Rabin-Karp Algorithm .

    vector<int> occurences;
    for (int i = 0; i + S - 1 < T; i++) { 
    long long cur_h = (h[i+S] + m - h[i]) % m; 
    if (cur_h == h_s * p_pow[i] % m)
        occurences.push_back(i);
    }

I’m not able to figure out why h_s is multiplied with prime number power. Like this is hash value of pattern for which we are searching then what is need to multiply it again here?

2

Write polynomial hash of string and pattern. Polynomial of pattern always start with s[0]*p_pow[0] where as text start with t[i]*p_pow[i].