java - 为什么为相同的subString生成两个不同的哈希值，我该怎么做才能解决这个问题？

我编写了以下代码，以尝试简单地实现Rabin-Karp算法。

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

像上面的代码中那样计算滚动哈希在纸张上效果很好，但是我无法弄清楚为什么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滚动哈希将为27864。

最佳答案

让我们考虑rollHash的结构。假设A[]是needle的char值的任何数组。在第一个循环rollHash之后

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

在第二个循环中

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)是一个相对昂贵的函数，并且很容易消除它的使用。