# Rolling Hash calculation with Horner's method

I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial.

I have a character array derived from a string

String s = "hi how are you"

char[] array = {'h' , 'i', ' ',  'h', 'o', 'w', ' ',  'a', 'r', 'e,' ' ', 'y', 'o', 'u'}


I want to generate hash for set of characters, in successive windows of same size, example 0..3, 1..4, 2..5 etc.

Let's say I want to generate hash for characters 0(inclusive) through 3(exclusive), polynomial is $ax^2+bx+c$ where $a = array[0], b = array[1], c = array[2]$ . I am using following code.

int BASE = 31, MOD = 1000000007;

public long firstHash(char[] array, int start, int end) {
long hash = 0;
for (int i = start; i < end; i++) {
hash = (hash * BASE + array[i]) % MOD;
}
return hash;
}


I can see how this function evaluates the polynomial. I am using MOD to prevent overflows.

Now, if I want to generate hash for characters 1(inclusive) through 4(exclusive), it should be in constant time if we use hash generated for 0..3. New equation would be $bx^2+cx+d$. All that I have to do is subtract $ax^2$, multiply the result with x and add new element which is array[3]

$$previousHash = ax^2+bx+c\\ newHash = x\times (previousHash - ax^2)+d \\ = x\times (ax^2+bx+c-ax^2)+d \\ = bx^2+cx+d \\$$

I am using following code for successive hash generations

int BASE = 31, MOD = 1000000007;

public long successiveHash(char[] array, int start, int end, long previousHash) {
long base = 1;
for (int i = start; i < end - 1; i++) {
base = (base * BASE) % MOD;
}
return ((previousHash - ((array[start - 1] * base) % MOD)) * BASE + array[end - 1]) % MOD;
}


But, I am confused because of MOD. Although I know the multiplication and addition rule for % operator, I couldn't prove the successiveHash function. For smaller windows, it seems fine. But, if I generate hash for larger windows like 1..7, it is giving me negative values for hash.

I think I get the math part correct but implementation wrong.

Any help in correcting this function is of great help.

• See en.wikipedia.org/wiki/Rolling_hash. Questions about code are off-topic here. Make sure that all arithmetic is done with modular arithmetic. Beware of applying % to negative numbers, and beware of wraparound/overflow/underflow. – D.W. Apr 8 '18 at 3:38