Karp Rabin 中的质数和块长度

Question

我从该站点找到了一个 rabin karp 代码，并改为尝试。更改后的代码如下。您可以在 hashtable.txt 中查看单词及其哈希值。对于下面的示例 hashtable.txt 似乎是正确的。

但是当我将 M（块长度）更改为 150 时，我得到了错误的结果。例如在 hashtable.txt 中第一行和第六行必须相同但它们的哈希值不同。

或者当我将 q（质数）更改为 683303 时，它也会得到错误的结果。

rabin karp算法中素数和块长的关系是什么，结果错误的原因是什么？

#include<stdio.h>
#include<string.h>
#include <fstream>
#include <iostream>
// d is the number of characters in input alphabet
#define d 256 
int M = 80;
/*  
txt  -> text
q    -> A prime number
*/
using namespace std;

void writeTable(char *txt, int q)
{
ofstream myfile;
myfile.open ("hashtable.txt");
int N = strlen(txt);
int i, j;
int t = 0; // hash value for txt
int h = 1;

// The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M-1; i++)
    h = (h*d)%q;

// Calculate the hash value of pattern and first window of text
for (i = 0; i < M; i++)
{
    t = (d*t + txt[i])%q;
}

// Slide the pattern over text one by one 
for (i = 0; i <= N - M; i++)
{
    myfile << t <<" ";
    for (long z = i; z < M+i; z++){myfile<<txt[z];}myfile<<"\n";

    // Calulate hash value for next window of text: Remove leading digit, 
    // add trailing digit           
    if ( i < N-M )
    {
        t = (d*(t - txt[i]*h) + txt[i+M])%q;

        // We might get negative value of t, converting it to positive
        if(t < 0) 
          t = (t + q); 
    }
}

myfile.close();
}

/* Driver program to test above function */
int main()
{
    char *txt ="abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde";

int q = 683303;  // A prime number

writeTable(txt, q);

printf("finish");
getchar();
return 0;
}

Answer 1

计算

t = (d*(t - txt[i]*h) + txt[i+M])%q;

可以溢出。的最大值txt[i]是d-1，并且h可以和 一样大q-1。因此，如果(q-1)*(d-1)*d > INT_MAX，则存在整数溢出的可能性。这限制了可以安全选择的素数的大小INT_MAX/(d*(d-1)) + 1。

如果q大于 ，则对 的允许值构成限制M，即M必须满足

h <= INT_MAX/(d*(d-1))

以安全地防止溢出。

随着q = 683303和M = 80，你h = 182084，和

h*d*(d-1) = 182084 * 256 * 255 = 11886443520

比INT_MAXifint大，通常是 32 位宽。

如果您的ints 是 32 位宽，那么您从一开始就会溢出示例，因为h*256*97 = 4521509888 > 2147483647.