java - Rabin-Karp 滚动哈希

Question

在 Coursera 视频之一中，Rabin-Karp 滚动哈希 (http://en.wikipedia.org/wiki/Rolling_hash) 显示为:

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;
}

我认为这是错误的。我认为应该是:

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;
}

哪一个是正确的，为什么？

Answer 1

你的不可能是正确的，因为

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

对于任何长度超过 11 个字符的字符串，对于第一个长度为 11 或长度为 12 的字符，结果为 Integer.MAX_VALUE。例如，对于 20 个字符的字符串，当循环中的 i == 0 时，表达式为

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

10¹⁹ 不适合 int，因此转换的结果是 2147483647