Rabin-Karp stringa corrispondente non è corrispondenza

Question

Ho lavorato su una funzione di matching stringa di Rabin-Karp in C ++ e non sto ottenendo alcun risultato fuori di esso. Ho la sensazione che non sto calcolando alcuni dei valori in modo corretto, ma non so quali uno (s).

Prototype

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

Implementazione Funzione

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

Nella mia chiamata di funzione che passa 2359023141526739921 come la sequenza, 31415 come il modello, 10 come la radice, e 13 come il primo. Mi aspetto che ci sia una corrispondenza reale e un colpo spurio, ma non ho mai ottenere la dichiarazione di uscita dalla parte corrispondente della funzione. Che cosa sto facendo di sbagliato?

Grazie in anticipo, Madison

Answer 1

Il grande Gotcha nella codifica del Rabin Karp è il modulo operatore . Quando due numeri X e Y sono congruenti modulo Q allora (X% Q) dovrebbe uguale (Y% Q), ma il compilatore C ++ che si sta utilizzando saranno solo essere uguali se X e Y sono entrambi positivi o entrambi negativi. Se X è positivo e Y è negativo, allora (X% Q) sarà positivo (Y% Q) volontà negativo. Infatti (X% Q) -Q == (Y% Q) in questo caso.

Il lavoro attorno controlla per valori negativi dopo ogni modulo e se ci sono da aggiungere q alla variabile, in modo che il ciclo preelaborazione diventa:

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

t nelle principali esigenze del ciclo di avere un controllo simile aggiunto.

Answer 2

A meno che non abbia ridefinito ^, si sta calcolando XOR, non elevamento a potenza. Inoltre, si dovrebbe essere attenti a traboccare il valore massimo di un int prima di eseguire %.