Почему для разных подстрок генерируются два разных хеша и что я могу сделать, чтобы решить эту проблему?

Question

Я написал следующий код, чтобы попробовать упрощенную c реализацию алгоритма Рабина-Карпа.

 public int charToInt(int index, String str){
        return (int)str.charAt(index);
    }

    public int strStr(String haystack, String needle) {
        if(needle.length() == 0 ) return 0;
        int n = needle.length();
        int l = haystack.length();
        if(n > l) return -1;

        //choose large enough prime for hash
        final int prime = 257;

        //calculate reference hash of needle and first 'n' chars of haystack
        long refHash = 0, rollHash = 0;
        for(int i = 0; i < n; i++){
            refHash += charToInt(i,needle)*(long)Math.pow(prime,i);
            rollHash += charToInt(i,haystack)*(long)Math.pow(prime,i);
        }
        System.out.println("refHash: "+refHash);
        System.out.println("rolling hash: "+rollHash);
        if(refHash == rollHash) return 0;

        for(int i = n; i<l; i++){
            // oldhash - old initial char
            rollHash -= charToInt(i-n+1, haystack);
            // divide by prime.
            System.out.println("Perfect division anticipated "+ (double)rollHash/prime);
            rollHash /= prime;
            // add new char to hash at the end of pattern.
            rollHash += (charToInt(i,haystack)*(long)Math.pow(prime,n-1));

            if(refHash == rollHash) return i-n+2;
            System.out.println("rolling hash: "+rollHash);
        }
        return -1;
    }

Расчет скользящего га sh, как в приведенном выше коде, хорошо работает на бумаге, но я Я не могу понять, почему rollHash /= prime; не дает идеального деления.

Пример ввода / вывода, который, как мы надеемся, предоставит больше контекста. Входные данные

haystack: "hello"
needle: "ll"

Выходные данные

stdout:
refHash: 27864
rolling hash: 26061
Perfect division anticipated 101.01167315175097
rolling hash: 27857
Perfect division anticipated 107.9727626459144
rolling hash: 27863
Perfect division anticipated 107.99610894941634
rolling hash: 28634
Answer:
-1

Я надеялся на то, что Perfect division anticipated 107.9727626459144 эта строка выдаст 108, а rolling hash: 27863 значение га sh будет равно 27864.

Answer 1

Давайте подумаем о структуре rollHash. Пусть A[] будет любым массивом значений char needle. После первой l oop rollHash будет

A[0] + prime * A[1] + prime^2 * A[2] + ...

Во второй l oop

for(int i = n; i<l; i++){
        // oldhash - old initial char
        rollHash -= charToInt(i-n+1, haystack);
        // divide by prime.
        System.out.println("Perfect division anticipated "+ (double)rollHash/prime);
        rollHash /= prime;
        ....
}

В первой итерации i = n и вычитаем A [i -n + 1] = A [1]. Таким образом, rollhash теперь

A[0] + prime * A[1] + prime^2 * A[2] + ... - A[1]

, мы не ожидаем, что это делится на простое число.

Я думаю, что у вас отключена одна ошибка.

for(int i = n; i<l; i++){
        // oldhash - old initial char
        rollHash -= charToInt(i-n, haystack);    // **** changed
        // divide by prime.
        System.out.println("Perfect division anticipated "+ (double)rollHash/prime);
        rollHash /= prime;
        ....
}

Теперь это дает идеальное деление, и алгоритм, похоже, дает правильные результаты на ограниченных тестовых данных.

Также обратите внимание, что Math.pow(i,j) является относительно дорогой функцией, и ее довольно просто исключить.