Rabin-Karp String Matching no coincide

Question

He estado trabajando en una función de coincidencia de cadenas de Rabin-Karp en C++ y no obtengo ningún resultado. Tengo la sensación de que no estoy computando algunos de los valores correctamente, pero no sé cuál (es).

Prototipo

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

implementación de la función

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 pase 2359023141526739921 como la secuencia, 31415 como el patrón, 10 como la raíz, y 13, el principal. Espero que haya una coincidencia real y un golpe espurio, pero nunca obtengo el enunciado de salida de la parte coincidente de la función. ¿Qué estoy haciendo mal?

Gracias de antemano, Madison

Answer 1

El gran problema en la codificación de Rabin Karp es el modulo operator. Cuando dos números X e Y son módulo congruente Q entonces (X% Q) debería ser igual (Y% Q) pero en el compilador de C++ que está utilizando solo serán iguales si X e Y son positivos o ambos negativos. Si X es positivo e Y es negativo, entonces (X% Q) será positivo y (Y% Q) negativo. 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 hay alguno para añadir q para la variable, por lo que el 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 el bucle principal tiene que tener una cheque similar agregado.

Answer 2

A menos que haya redefinido ^, que es la computación XOR, no exponenciación. Además, debe tener cuidado de desbordar el valor máximo de int antes de realizar %.