Rabin-Karp文字列のマッチングは一致していません
-
08-10-2019 - |
質問
私はC ++でRabin-Karp Stringマッチング関数に取り組んできましたが、結果が得られていません。私はいくつかの値を正しく計算していないと感じていますが、どちらの値がわかりません。
プロトタイプ
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;
}
私の機能コールでは、シーケンスとして23590231526739921、パターンとして31415、基数として10、プライムとして13を渡します。私は実際の一致と1つの偽のヒットがあると期待していますが、関数の一致する部分から出力ステートメントを取得することはありません。私は何が間違っているのですか?
よろしくお願いします、マディソン
解決
Rabin Karpをコーディングする際の大きなGotchaは モジュロ演算子. 。 2つの数値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にも同様のチェックが追加される必要があります。
他のヒント
再定義されていない限り ^
, 、指数ではなくxorを計算しています。また、あなたは int
実行する前に %
.
所属していません StackOverflow