Rabin-Karp字符串匹配未匹配成功

Question

我正在使用C++编写Rabin-Karp字符串匹配函数，但是我没有得到任何结果。我感觉自己没有正确计算一些值，但我不知道是哪些值。

原型

void rabinKarp(string sequence, string pattern, int d, int q);

函数实现

void rabinKarp(string sequence, string pattern, int d, int q)
{
    //d is the |∑|
    //q is the prime number to use to lessen spurious hits
    int n = sequence.length(); //Length of the sequence
    int m = pattern.length(); //Length of the pattern
    double temp = static_cast<double> (m - 1.0);
    double temp2 = pow(static_cast<double> (d), temp); //Exponentiate d
    int h = (static_cast<int>(temp2)) % q; //High Order Position of an m-digit window
    int p = 0; //Pattern decimal value
    int t = 0; //Substring decimal value
    for (int i = 1; i < m; i++) { //Preprocessing
        p = (d*p + (static_cast<int>(pattern[i]) - 48)) % q;
        t = (d*t + (static_cast<int>(sequence[i])-48)) % q;
    }
    for (int s = 0; s < (n-m); s++) { //Matching(Iterate through all possible shifts)
        if (p == t) {
            for (int j = 0; j < m; j++) {
                if (pattern[j] == sequence[s+j]) {
                    cout << "Pattern occurs with shift: " << s << endl;
                }
            }
        }
        if (s < (n-m)) {
            t = (d*(t - ((static_cast<int>(sequence[s+1]) - 48)*h)) + (static_cast<int>(sequence[s + m + 1]) - 48)) % q;
        }
    }
    return;
}

在我的函数调用中，我将2359023141526739921作为序列、31415作为模式、10作为基数和13作为素数传递。我期望会有一个实际匹配和一个伪命中，但是我从函数匹配部分永远没有得到输出语句。我哪里做错了？

谢谢，Madison

- Madison S

Answer 1

在编写 Rabin Karp 时，最大的陷阱是模运算符。当两个数字 X 和 Y 模 Q 同余时，(X % Q) 应该等于 (Y % Q)，但是在您使用的 C++ 编译器上，只有当 X 和 Y 都为正数或都为负数时它们才相等。如果 X 是正数而 Y 是负数，则 (X % Q) 将为正数而 (Y % Q) 将为负数。实际上，在这种情况下 (X % Q)-Q == (Y % Q)。

解决方法是在每次模运算后检查负值，如果有任何负值，则将 q 添加到变量中，因此您的预处理循环变成：

    p = (d*p + pattern[i]) % q;
    if ( p < 0 ) p += q;
    t = (d*t + sequence[i]) % q;
    if ( t < 0 ) t += q;

在主循环中，需要添加类似的检查。

- paperhorse

Answer 2

除非您重新定义了^，否则它计算的是异或，而不是指数。此外，在执行%之前，您应该注意不要溢出int的最大值。

- jonderry

---

谢谢！这对我解决h不正确的问题有所帮助。我不知道^运算符没有定义为指数。但仍然没有输出 :( - Madison S

我会验证其中的小部分是否按预期运行，而不是试图一次性让所有东西都正常工作。这将帮助您逐个找到错误。 - jonderry

通过使用GDB逐步调试，我找到了罪魁祸首：在第二个for循环中重新计算t导致出现负数。据我所知，除此之外，其他所有内容都按预期工作。 - Madison S