Rabin-Karp哈希碼太大

Question

如何處理滾動哈希Rabin-Karp算法中的大哈希碼值？我使用模運算來避免負數，但是當哈希碼超過我的模數（N = 83559671）時會出現問題。我將我的基數設置爲素數（計算哈希碼的數字）以及模數（真的很大），但它不適用於長字符串。任何人都可以看到問題嗎？

這是我的代碼。

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

爲什麼不把你的字符串當作一個多項式？假設您有一個長度爲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)是一個多項式，我們可以使用​​來計算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更多的信息。

Answer 2

根本不需要做模數。這裏有一個演示：

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