0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 8 '18 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.