Rabin-Karp stringa corrispondente non è corrispondenza
-
08-10-2019 - |
Domanda
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
Soluzione
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.
Altri suggerimenti
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 %
.