Rabin-Karp rolling hash

Question

In one of the Coursera videos the Rabin-Karp rolling hash (http://en.wikipedia.org/wiki/Rolling_hash) is shown as:

public static long getHash(String S)
{
    long H = 0;

    for (int i = 0; i < S.length(); i++)
        H = (H * 10 + S.charAt(i)) % 997;

    return H;
}

I think it's wrong. I think it should be :

public static long getHash(String S)
{
    long H = 0;

    for (int i = 0; i < S.length(); i++)
        H = (S.charAt(i) * (int)Math.pow(10, (S.length() - i - 1)) + H) % 997;

    return H;
}

Which one is correct and why?

Answer 1

Yours cannot possibly be right because

(int)Math.pow(10, (S.length() - i - 1))

for any string longer than 11 characters results in Integer.MAX_VALUE, for the first length-11 or length-12 characters. For example, for a 20-character string, when i == 0 in your loop, this is expression is

(int)Math.pow(10, (20-0-1))

10¹⁹ does not fit in an int, so the result of the cast is 2147483647