es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Algoritmo de Rabin-Karp en c++

Estoy tratando de entender la implementación del algoritmo Rabin-Karp. d es el número de caracteres en el alfabeto de entrada, pero si reemplazo 0 o cualquier otro valor en lugar de 20, no afectará nada. ¿Por qué está sucediendo esto así?

“`cpp
// Algoritmo Rabin-Karp en C++

#include <string.h>
#include

using namespace std;

#define d 20

void rabinKarp(char pattern[], char text[], int q) {
int m = strlen(pattern);
int n = strlen(text);
int i, j;
int p = 0;
int t = 0;
int h = 1;

for (i = 0; i < m - 1; i++)
h = (h * d) % q;

// Calcular el valor hash para el patrón y el texto
for (i = 0; i < m; i++) {
p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}

// Encontrar la coincidencia
for (i = 0; i <= n – m; i++) {
if (p == t) {
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}

    if (j == m)
        cout << "El patrón se encuentra en la posición: " << i + 1 << endl;
}

if (i < n - m) {
    t = (d * (t - text[i] * h) + text[i + m]) % q;

    if (t < 0)
        t = (t + q);
}

}
}

int main() {

// char text[] = “ABCCDXAEFGX”;
char text[] = “QWERTYUIOPASDFGHJKLXQWERTYUIOPASDFGHJKLX”;
char pattern[] = “KLXQW”;
int q = 13;
rabinKarp(pattern, text, q);
}</string.h>

Tags:  , ,

Answer

  1. Avatar for davy.ai

    El valor de la constante “d” representa el número de caracteres en el alfabeto de entrada. En esta implementación, se usa el valor de “d” como 20. Sin embargo, cualquier otro valor puede ser utilizado siempre y cuando sea un número primo o co-primo con el valor módulo elegido “q”. Esto se debe a que el algoritmo Rabin-Karp utiliza la función hash polinomial, que implica multiplicar cada caracter de entrada por una constante “d” elevada a una potencia, y sumarlo al resultado. El valor de “d” afecta la distribución de los códigos hash, pero siempre y cuando sea un número primo o co-primo, debería producir una buena distribución de los códigos hash, lo cual es esencial para reducir la frecuencia de colisiones. Por lo tanto, reemplazar 20 por cualquier otro número primo o co-primo no debería afectar la corrección ni la eficiencia del algoritmo.

Comments are closed.