2

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

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

4

1 回答 1

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 19不适合 a int，所以演员表的结果是2147483647

于 2013-10-11T22:28:50.703 回答