Rabin-Karp String Matching passt nicht

Question

Ich habe an einer Rabin-Karp String-Matching-Funktion in C++ gearbeitet und ich bekomme keine Ergebnisse daraus. Ich habe das Gefühl, dass ich einige der Werte nicht korrekt berechne, aber ich weiß nicht, welche (s).

Prototype

void rabinKarp(string sequence, string pattern, int d, int q); 

Funktion Implementierung

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

In meiner Funktion Anruf ich 2359023141526739921 als Folge passieren, 31415 wie das Muster, 10 als radix und 13 als die prime. Ich erwarte, dass es eine tatsächliche Übereinstimmung und einen zufälligen Treffer gibt, aber ich bekomme nie die Ausgabeanweisung von dem passenden Teil der Funktion. Was mache ich falsch?

Vielen Dank im Voraus, Madison

Answer 1

Das große Gotcha in der Codierung der Rabin Karp ist die modulo operator. Wenn zwei Zahlen X und Y kongruent modulo Q sind, dann sollte (X% Q) gleich sein (Y% Q), aber auf dem C++ - Compiler, den Sie verwenden, sind sie nur gleich, wenn X und Y beide positiv oder beide negativ sind. Wenn X positiv und Y negativ ist, ist (X% Q) positiv und (Y% Q) negativ. Tatsächlich (X% Q) - Q == (Y% Q) in diesem Fall.

Die Arbeit um für negative Werte nach jedem Modulo zu überprüfen ist, und wenn es q auf die Variable hinzuzufügen ist, so dass Ihre Vorverarbeitung Schleife wird:

p = (d*p + pattern[i]) % q; 
    if (p < 0) p += q; 
    t = (d*t + sequence[i]) % q; 
    if (t < 0) t += q; 

t in der Hauptschleife muss eine haben ähnliche Prüfung hinzugefügt.

Answer 2

Es sei denn, Sie ^ neu definiert haben, es xor ist die Berechnung, Potenzierung nicht. Außerdem sollten Sie vorsichtig sein, wenn Sie den Höchstwert von int überschreiten, bevor Sie % ausführen.