Гашиш Рабина-Карпа

В одном из видеороликов Coursera скользящий хеш Рабина-Карпа (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;
}

Какой из них правильный и почему?


java rabin-karp
person good_evening    schedule 11.10.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваше не может быть правильным, потому что

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

для любой строки длиннее 11 символов приводит к Integer.MAX_VALUE, для первой длины-11 или длины-12 символов. Например, для 20-символьной строки, когда i == 0 в вашем цикле, это выражение

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

1019 не помещается в int, поэтому результатом приведения является 2147483647

person Jim Garrison    schedule 11.10.2013
comment
Почему нет? На каждой итерации значение H всегда находится в диапазоне 0 - 996. Вы правы, это не совсем похоже на описание из Википедии, но с той лишь разницей, что она обрабатывает символы в обратной последовательности. a^0 применяется к самому левому символу, а не к самому правому. - person Jim Garrison; 12.10.2013