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;