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

Question

Según el wikipedia entry en el algoritmo de concordancia de cadenas Rabin-Karp, se puede usar 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 aún no entiendo cómo podemos conservar la complejidad O (n) cuando buscamos patrones con diferente longitud simultáneamente. Por favor alguien puede arrojar algo de luz sobre esto?

Edit (diciembre de 2011):

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

Answer 1

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

Mientras que la construcción de el valor hash, se puede comprobar si hay una coincidencia en el conjunto de hashes de cuerda. Aka, el valor actual de hash. 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 de cadena máxima 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 m pasos. En cada paso hay un valor de hash temporal que podemos buscar (complejidad O (1)) en el conjunto de hashes. Todos los hash tendrán el mismo tamaño, es decir, 32 bit.

Actualización 2: un amortizado (promedio) O (n) tiempo de la complejidad?

Arriba he dicho que m debe tener la longitud máxima de la cadena. Resulta que podemos explotar todo lo contrario.
Con hashing for shifting substring search y un tamaño fijo m podemos lograr O (n) complejidad.

Si tenemos cadenas de longitud variable, podemos establecer m con la longitud mínima de la cadena. Además, en el conjunto de hash no asociamos un hash con toda la cadena, sino con los primeros m caracteres.
Ahora, mientras buscamos en el texto comprobamos 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).

Answer 2

Se debe a que los valores hash de las subcadenas se relacionan 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) realiza O (m) tiempo en una cadena de longitud m. Pero una vez que tenga que, computación 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, tiempo lineal.

Here's a link donde esto se describe con más detalle (véase, por ejemplo la sección "Lo que hace Rabin-Karp rápido?")