Rabin-Karp哈希码太大

Question

如何处理滚动哈希Rabin-Karp算法中较大的哈希码值？任何人都能看到问题所在吗？

这是我的代码。

   public static void main(String [] args){

       int P = 13;         // base
       long M = 83559671;
       long iHash = 0;    
       String word = "abcbadccaaaabbbb";
       int WINDOW = 9;

       for(int i = 0; i < WINDOW; i++){
            iHash = int_mod(int_mod(iHash*P, M) + word[i], M);
       }

       for(int i = WINDOW; i < word.length; i++){
            iHash = int_mod(iHash - word[i-WINDOW] * get_pow(P, WINDOW-1, M), M);
            iHash = int_mod(iHash * P, M);
            iHash = int_mod(iHash + word[i], M);
       }

   }
   public static long get_pow(int p, int t, long M){
        long a = 1;
        for(int i = 0 ; i < t; i++){
              a = int_mod(a * p, M);
        }
        return a;
   }

   public static long int_mod(long a, long b){
        return (a % b+ b) % b;
   }

问题是，当我有任何长度大于8的字符串时，该字符串的哈希码就超过了模数83559671，这会导致我在进行比较时得到错误的答案。任何较短的字符串都可以正常工作。

Answer 1

你根本不需要做模数。下面是一个演示：

public class Foo {
  private static int hash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
      hash *= 31;
      hash += s.charAt(i);
    }
    return hash;
  }

  public static void main(String[] args) {
    String s1 = "abcdefghij";
    String s2 = s1.substring(1) + "k";
    int pow = 1;
    for (int i = 0; i < s1.length(); i++) {
      pow *= 31;
    }
    System.out.printf("hash(%s) = %d%n", s1, hash(s1));
    System.out.printf("hash(%s) = %d%n31 * hash(%s) - (31^%d * %s) + %s = %s%n",
        s2,
        hash(s2),
        s1,
        s1.length(),
        s1.charAt(0),
        s2.charAt(s2.length() - 1),
        31 * hash(s1) - (pow * s1.charAt(0)) + s2.charAt(s2.length() - 1));
  }
}

下面(正确地)打印出：

hash(abcdefghij) = -634317659
hash(bcdefghijk) = 21611845
31 * hash(abcdefghij) - (31^10 * a) + k = 21611845

Answer 2

你为什么不把你的弦当作多项式呢？假设您有一个长度为n的字符串S。现在看一下下面的函数：F(x) = S[0]*x^(n-1) + S[1]*x^(n-2) + ... + S[i]*x^(n-i-1) + ... + S[n - 2]*x + S[n-1]。如果您试图计算F(P)，其中P是您的代码片段的基数，会发生什么？好的，你会得到字符串S的拉宾-卡普散列。但是因为F(x)是一个多项式，所以我们可以使用Horner's rule来计算F(P)。结果值可能非常大，因此我们使用模运算：

static final long M = 83559671;
static final int Base = 13;

static long hash(String s, int from, int to) {
    int iHash = 0;
    for(int i = from; i < to; i++) {
        iHash *= Base;
        iHash += s.charAt(i);
        iHash %= M;
    }
    return iHash;
}

您可以使用此函数来获取要在文本中找到的字符串的哈希。和文本中的初始窗口。然后，您可以移位窗口并重新计算散列：

static void find(String pattern, String text) {
    if(text.length() < pattern.length()) return;
    int len = pattern.length();
    long ph = hash(pattern, 0, len);
    long h = hash(text, 0, len);
    long basePower = mpow(Base, len);

    if(h == ph) System.out.println("match at 0");
    for(int i = len; i < text.length(); i++) {
        h *= Base;
        h += text.charAt(i);
        h -= basePower * text.charAt(i - len);
        h = mod(h);
        if(h == ph) System.out.println("match at " + (i - len + 1));
    }
}

static long mod(long a) {
    a %= M;
    if(a < 0) {
        a += M;
    }
    return a;
}

static long mpow(long x, int k) {
    long result = 1;
    for(; k > 0; k >>= 1) {
        if(k % 2 == 1) {
            result = mod(result * x);
        }
        x = mod(x * x);
    }
    return result;
}

public static void main(String[] args) {
    find("abracadabra", "abracadabracadabra");
}

有关此方法的更多信息，我建议参考CLRS。