horner's rule and rabin fingerprint
F = a0 * x^0 + a1 * x^1 + a2 * x^2 + … + an * x^n F is an nth degree polynomial
F = ( ( (an * x) + an-1) * x) + an-2) * x …
# A is an array of coefficients
# evaluates nth degree polynomial with coefficients at x
def Horner(A, x : int) -> int:
ans = 0
for a in A[::-1]:
ans = (ans + a) * x
return ans
This can be quite useful in other areas, like rabin karp string matching. The polynomial can be updated in a sliding window fashion instead of recomputed everytime.
code for initializing polynomial hash
// s : string with length N > M
// si_h1 : hash of first M length substring
// A1 : our coefficient
ull si_h1 = s[0] - 'a';
for (int i = 1;i < M;++i) {
si_h1 = (si_h1 * A1) % MOD;
si_h1 = (si_h1 + (ull)(s[i] - 'a')) % MOD;
}
“sliding” the hash to the right
si_h1 = (si_h1 - (big_term1 * (ull)(s[i] - 'a')) % MOD) % MOD;
si_h1 = (si_h1 * A1) % MOD;
si_h1 = (si_h1 + (ull)(s[i + M] - 'a')) % MOD;