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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.