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; 
} 

私は、基数として10、パターンとして31415、シーケンスとして2359023141526739921を渡し、など13プライム。私は1つの実際のマッチと1つの偽のヒットがあることを期待していますが、関数の一致する部分から出力ステートメントを取得することはありません。私は間違って何をしていますか？あなたが^を再定義してきた場合を除き、事前に

おかげで、マディソン

は

Answer 1

Rabin Karpをコーディングする際の大きな問題はmodulo operatorです。 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; 

トンを持っている必要があります同様のチェックが追加されました。

Answer 2

、それは排他的論理和を計算され、累乗ではありません。また、%を実行する前に、intの最大値のオーバーフローに注意する必要があります。