5

私は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を渡します。実際の一致が1つ、スプリアスヒットが1つあると予想しますが、関数の一致部分から出力ステートメントを取得することはありません。私は何が間違っているのですか？

よろしくお願いします、マディソン

4

2 に答える 2

8

ラビンカープをコーディングする際の大きな落とし穴は、モジュロ演算子です。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には、同様のチェックを追加する必要があります。

于 2010-12-04T04:26:40.660 に答える
5

再定義しない限り^、べき乗ではなく、xorを計算しています。intまた、を実行する前に、anの最大値がオーバーフローすることに注意する必要があります%。

于 2010-12-04T02:00:25.830 に答える