algoritmo - rabin karp algorithm

Usando Rabin-Karp para buscar múltiples patrones en una cuerda

Question

De acuerdo con la entrada de wikipedia en el algoritmo de coincidencia de cadenas Rabin-Karp, se puede utilizar para buscar varios patrones diferentes en una cadena al mismo tiempo mientras se mantiene la complejidad lineal. Está claro que esto se hace fácilmente cuando todos los patrones son de la misma longitud, pero todavía no entiendo cómo podemos preservar la complejidad O (n) al buscar patrones con diferentes longitudes simultáneamente. ¿Alguien puede arrojar algo de luz sobre esto?

Edición (diciembre 2011):

El artículo de wikipedia se ha actualizado desde entonces y ya no afirma que coincida con múltiples patrones de diferente longitud en O (n).

Answer 1

Es porque los valores de hash de las subcadenas están relacionados matemáticamente. El cálculo del hash H (S, j) (el hash de los caracteres que comienzan desde la posición jth de la cadena S ) lleva el tiempo O (m) en una cadena de longitud m . Pero una vez que tienes eso, el cálculo de H (S, j + 1) se puede hacer en tiempo constante, porque H (S, j + 1) se puede expresar como una función de H (S, j) .

O (m) + O (1) => O (m) , es decir, tiempo lineal.

Aquí hay un enlace donde se describe con más detalle (ver, por ejemplo, la sección "¿Qué hace que Rabin-Karp sea más rápido?")

Answer 2

No estoy seguro de si esta es la respuesta correcta, pero de todos modos:

Mientras construimos el valor de hash, podemos verificar si hay una coincidencia en el conjunto de hashes de cadena. Aka, el valor hash actual . La función / código hash generalmente se implementa como un bucle y dentro de ese bucle podemos insertar nuestra búsqueda rápida.

Por supuesto, debemos elegir m para tener la longitud máxima de la cadena del conjunto de cadenas.

Actualización: de Wikipedia,

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

Calculamos el hash actual en m pasos. En cada paso hay un valor de hash temporal que podemos buscar (O (1) complejidad) en el conjunto de hashes. Todos los hashes tendrán el mismo tamaño, es decir, 32 bits.

Actualización 2: ¿ una complejidad de tiempo O (n) amortizada (promedio)?

Arriba dije que m debe tener la longitud máxima de la cuerda. Resulta que podemos explotar lo contrario.
Con el hashing para la búsqueda de subcadenas cambiantes y un tamaño de m fijo podemos lograr O (n) complejidad.

Si tenemos cadenas de longitud variable, podemos establecer m en la longitud de cadena mínima. Además, en el conjunto de hashes no asociamos un hash con toda la cadena, sino con los primeros m-caracteres de la misma.
Ahora, mientras buscamos en el texto, verificamos si el hash actual está en el conjunto de hash y examinamos las cadenas asociadas para una coincidencia.

Esta técnica aumentará las falsas alarmas, pero en promedio tiene una complejidad de tiempo O (n).