Rabin-Karp 不适用于大素数（给出错误的输出）

Question

所以我正在解决 this 问题（Rabin Karp 的算法）并写下了这个解决方案：

private static void searchPattern(String text, String pattern) {
    int txt_len = text.length(), pat_len = pattern.length();
    int hash_pat = 0, hash_txt = 0; // hash values for pattern and text's substrings
    final int mod = 100005;         // prime number to calculate modulo... larger modulo denominator reduces collisions in hash
    final int d = 256;              // to include all the ascii character codes
    int coeff = 1;                  // stores the multiplier (or coeffecient) for the first index of the sliding window

    /* 
     * HASHING PATTERN:
     * say text    = "abcd", then
     * hashed text = 256^3 *'a' + 256^2 *'b' + 256^1 *'c' + 256^0 *'d'
     */

    // The value of coeff would be "(d^(pat_len - 1)) % mod"
    for (int i = 0; i < pat_len - 1; i++)
        coeff = (coeff * d) % mod;

    // calculate hash of the first window and the pattern itself
    for (int i = 0; i < pat_len; i++) {
        hash_pat = (d * hash_pat + pattern.charAt(i)) % mod;
        hash_txt = (d * hash_txt + text.charAt(i)) % mod;
    }

    for (int i = 0; i < txt_len - pat_len; i++) {
        if (hash_txt == hash_pat) {
            // our chances of collisions are quite less (1/mod) so we dont need to recheck the substring
            System.out.println("Pattern found at index " + i);
        }
        hash_txt = (d * (hash_txt - text.charAt(i) * coeff) + text.charAt(i + pat_len)) % mod; // calculating next window (i+1 th index)

        // We might get negative value of t, converting it to positive
        if (hash_txt < 0)
            hash_txt = hash_txt + mod;
    }
    if (hash_txt == hash_pat) // checking for the last window
        System.out.println("Pattern found at index " + (txt_len - pat_len));
}

现在，如果 mod = 1000000007，此代码将无法正常工作，而一旦我们采用其他一些质数（足够大，如 1e5+7），代码就会神奇地开始工作！

代码逻辑失败的行是：

hash_txt = (d * (hash_txt - text.charAt(i) * coeff) + text.charAt(i + pat_len)) % mod;

谁能告诉我为什么会这样？？？也许这是一个愚蠢的疑问，但我就是不明白。

Answer 1

在Java中，int是一个32位整数。如果用这样的数字进行的计算在数学上产生了需要更多二进制数字的结果，那么多余的数字将被默默地丢弃。这叫做溢出。

为避免这种情况，Rabin-Karp 算法在每一步中对结果取模一些素数进行缩减，从而使数字保持足够小以使下一步不会溢出。为此，选择的素数必须足够小

d * (hash + max(char) * coeff) + max(char)) < max(int)

自

0 ≤ hash < p,
1 ≤ 系数 < p,
最大（字符）= 2¹⁶
最大（整数）= 2³¹

任何小于 2⁷=128 的素数都可以。对于更大的素数，这取决于它们的系数最终是什么，但即使我们 select 一个具有最小可能系数 = 1 的素数也不能超过 2²³，这比你使用的质数小得多。

在实践中，人们因此将 Rabin-Karp 与一个比字符类型大得多的整数数据类型一起使用，例如 long（64 位）。然后，任何 < 2³⁹ 的素数都可以。

即便如此，如果值得注意的是你的推理

our chances of collisions are quite less (1/mod) so we dont need to recheck the substring

是有缺陷的，因为概率不是随机决定的，而是由被检查的字符串决定的。除非您知道输入的概率分布，否则您无法知道失败的概率是多少。这就是 Rabin-Karp 重新检查字符串以确保的原因。

Rabin-Karp 不适用于大素数（给出错误的输出）

Rabin-Karp not working for large primes (gives wrong output)

java

algorithm

modulo

rabin-karp