La correspondance de chaîne de Rabin-Karp ne correspond pas

Question

J'ai travaillé sur une fonction de correspondance de chaîne Rabin-Karp en C++ et je n'obtiens aucun résultat. J'ai le sentiment que je ne calcule pas correctement certaines valeurs, mais je ne sais pas lequel (s).

Prototype

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

Fonction Application

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

Dans mon appel de fonction, je passe 2359023141526739921 que la séquence, 31415 en tant que motif, 10 comme la base, et 13 en tant que premier. Je m'attends à ce qu'il y ait une correspondance réelle et une frappe parasite, mais je n'obtiens jamais l'instruction de sortie de la partie correspondante de la fonction. Qu'est-ce que je fais mal?

Merci à l'avance, Madison

Answer 1

Le grand avantage dans le codage du Rabin Karp est le modulo operator. Lorsque deux nombres X et Y sont congrus modulo Q alors (X% Q) devrait être égal à (Y% Q) mais sur le compilateur C++ que vous utilisez, ils ne seront égales que si X et Y sont tous deux positifs ou négatifs. Si X est positif et Y est négatif alors (X% Q) sera positif et (Y% Q) sera négatif. En fait (X% Q) -Q == (Y% Q) dans ce cas.

Le travail est autour de vérifier les valeurs négatives après chaque modulo et s'il y en a pour ajouter q à la variable, de sorte que votre boucle de pré-traitement devient:

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

t dans la boucle principale doit avoir une vérification similaire ajoutée.

Answer 2

Sauf si vous avez redéfinissez ^, il calculait XOR, non Exponentiation. En outre, vous devez faire attention à déborder la valeur maximale d'un int avant d'exécuter %.