gpt4 book ai didi

c++ - Rabin-Karp 字符串匹配不匹配

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:00:41 34 4
gpt4 key购买 nike

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

原型(prototype)

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 作为素数。我希望有一个实际匹配和一个虚假命中,但我从来没有从函数的匹配部分得到输出语句。我做错了什么?

提前致谢,麦迪逊

最佳答案

编写 Rabin Karp 的最大陷阱是 modulo operator .当两个数字 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;

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

关于c++ - Rabin-Karp 字符串匹配不匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4351404/

34 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com