Rabin-Karp chaîne correspondant ne correspond pas à

Question

Je travaille sur une fonction de correspondance de chaîne Rabin-Karp en C ++ et je ne reçois pas de résultats hors de lui. J'ai le sentiment que je connais pas correctement calculer certaines valeurs, mais je ne pas lequel (s).

Prototype

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

Mise en œuvre de la fonction

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, en tant que motif 31415, 10 comme la base, et 13 que le premier. Je pense qu'il y ait un match réel et un coup faux, mais je ne reçois jamais la déclaration de sortie de la partie correspondante de la fonction. Qu'est-ce que je fais mal?

Merci à l'avance, Madison

Answer 1

Le grand Gotcha dans le codage du Rabin Karp est le modulo opérateur. Lorsque deux nombres X et Y sont congruents modulo Q alors (X% Q) doit être égal (Y% Q), mais sur le compilateur C ++ que vous utilisez ils ne seront égaux si X et Y sont tous deux positifs ou tous deux négatifs. Si X est positif et Y est négatif, (X% Q) sera positif et (Y% Q) volonté négative. 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 ajouter q à la variable, de sorte que votre boucle prétraiter 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 les principaux besoins en boucle d'avoir un contrôle similaire ajouté.

Answer 2

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