0

我编写了以下代码来尝试 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。

4

1 回答 1

0

Lets think about the structure of rollHash. Let A[] be any array of the char values of needle. After the first loop rollHash will be

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

In the second loop

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

In the first iteration i = n and we subtract A[i-n+1] = A[1]. So rollhash is now

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

we would not expect this to be divisible by prime.

I think you have an off by one error.

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

This now give perfect divisions and the algorithm seems to give the right results on limited test data.

Also note Math.pow(i,j) is a relatively expensive function and its quite easy to eliminate its use.

于 2020-02-02T04:38:03.977 回答