Rabin-Karp弦匹配不匹配
-
08-10-2019 - |
题
我一直在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作为radix,13作为素数。我希望有一场实际的比赛和一个虚假的命中,但是我从未从功能的匹配部分获得输出语句。我究竟做错了什么?
预先感谢麦迪逊
解决方案
编码Rabin Karp的大垃圾是 Modulo操作员. 。当两个数字x和y是一致的模量q时,(x%q)应等于(y%q),但是在C ++编译器上,您使用它们仅在x和y都是正面或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需要添加类似的检查。
其他提示
除非您重新定义 ^
, ,它是计算XOR,而不是指控。另外,您应该谨慎地溢出一个 int
在您表演之前 %
.
不隶属于 StackOverflow