Rabin-Karp cadena coincidente no es coincidente

Question

He estado trabajando en una función de cadena coincidente Rabin-Karp en C ++ y ahora no recibo ningún resultado fuera de él. Tengo la sensación de que no estoy calculando algunos de los valores correctamente, pero no sé cuál (s).

Prototipo

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

Implementación de funciones

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

En mi llamada a la función que pasan 2359023141526739921 como la secuencia, como el patrón 31415, 10 como la raíz, y 13 como la primera. Me espera que haya un partido real y un hit espuria, pero nunca me da la instrucción de salida de la parte correspondiente de la función. ¿Qué estoy haciendo mal?

Gracias de antemano, Madison

Answer 1

La gran Gotcha en la codificación de la Rabin Karp es la módulo operador . Cuando dos números X e Y son congruentes módulo Q entonces (X% Q) debe ser igual a (Y% Q), pero en el compilador de C ++ que está utilizando sólo serán iguales si X e Y son ambos positivos o ambos negativos. Si X es positiva e Y es negativa, entonces (X% Q) será positivo y (Y% Q) negativo voluntad. De hecho (X% Q) -Q == (Y% Q) en este caso.

La solución es comprobar si hay valores negativos después de cada módulo y si los hay q añadir a la variable, por lo que su bucle de procesamiento previo se convierte en:

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

t en las principales necesidades de bucle para tener un control similares agregó.

Answer 2

A menos que haya redefinido ^, se está calculando XOR, no exponenciación. Además, se debe tener cuidado con desbordar el valor máximo de una int antes de realizar %.