Rabin-Karp String Matching nicht passende

Question

Ich habe auf einer Rabin-Karp String-Matching-Funktion in C ++ arbeiten, und ich bin immer noch keine Ergebnisse aus ihn heraus. Ich habe das Gefühl, dass ich nicht richtig einige der Werte, die Berechnung, 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 meinem Funktionsaufruf übergebe ich 2359023141526739921 wie die Sequenz, 31415 wie das Muster, 10 als radix und 13 als Haupt. Ich erwarte, dass es ein tatsächliches Spiel und ein unechter Schlag sein, aber ich habe nie die Ausgabeanweisung von dem Anpassungs Teil der Funktion erhalten. Was mache ich falsch?

Vielen Dank im Voraus, Madison

Answer 1

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

Die Arbeit um ist für negative Werte nach jedem Modulo zu prüfen und falls vorhanden q in die Variable hinzuzufügen, 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 Bedürfnisse haben eine ähnliche Prüfung hinzugefügt.

Answer 2

Wenn Sie ^ neu definiert haben, wird die Berechnung xor, nicht Potenzierung. Außerdem sollten Sie vorsichtig sein, um den maximalen Wert eines int überfüllt, bevor Sie % durchführen.