El uso de Rabin-Karp para buscar patrones múltiples en una cadena

Question

De acuerdo con la wikipedia entrada en Rabin-Karp algoritmo cadena coincidente, puede ser usado para observar varios patrones diferentes en una cadena al mismo tiempo, manteniendo al mismo tiempo 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 O (n) la complejidad en la búsqueda de patrones con diferente longitud de forma simultánea. Por favor alguien puede arrojar algo de luz sobre esto?

Editar (diciembre de 2011):

El artículo de Wikipedia desde entonces ha sido actualizado y ya no reclamaciones para que coincida con múltiples patrones de diferente longitud en O (n).

Answer 1

No estoy seguro si esto es la respuesta correcta, pero de todos modos:
Si bien la construcción el valor hash, podemos comprobar si hay una coincidencia en el conjunto de hashes de cuerda. Aka, el actuales valor hash. La función hash / código se implementa normalmente como un bucle y en el interior de ese bucle podemos insertar nuestro Búsqueda rápida.
Por supuesto, hay que recoger m tener la longitud máxima de 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 actual de hash en los pasos m. En cada paso hay un temporal valor hash que podemos mirar hacia arriba (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 funcionalidad (media) amortizado O (n) la complejidad del tiempo?
Por encima de lo dicho que m debe tener la longitud máxima de cadena. Resulta que podemos explotar todo lo contrario.
Con hash para el desplazamiento de búsqueda y una subcadena m fijo tamaño podemos lograr O (n) la complejidad.
Si tenemos cadenas de longitud variable podemos establecer m a la longitud mínima de cadena. Además, en el conjunto de valores hash no nos asociamos un hash con toda la cadena, pero con los m primeros caracteres de la misma.
Ahora, mientras se busca el texto, comprobamos si el hash actual está en el conjunto hash y examinamos las cadenas asociadas para un partido.
Esta técnica aumentará las falsas alarmas, pero en promedio se tiene O (n) tiempo de complejidad.

Answer 2

Se debe a que los valores hash de las subcadenas están relacionadas matemáticamente. Cálculo de la hash de H (S, j) (el hash de los caracteres a partir de la posición j-ésima de cadena S ) toma O (m) tiempo en una cadena de longitud m . Pero una vez que tienes eso, el cálculo de H (S, j + 1) se puede hacer en un 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, el tiempo lineal.

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