En utilisant Rabin-Karp pour rechercher plusieurs modèles dans une chaîne

Question

Selon le wikipedia entrée sur l'algorithme de correspondance de chaîne Rabin-Karp, il peut être utilisé pour rechercher plusieurs modèles différents dans une chaîne en même temps tout en conservant la complexité linéaire. Il est clair que cela se fait facilement lorsque tous les motifs sont de la même longueur, mais je ne comprends toujours pas comment nous pouvons préserver O (n) complexité lors de la recherche de modèles avec différentes longueurs simultanément. Quelqu'un peut-il s'il vous plaît éclairer à ce sujet?

Modifier (Décembre 2011):

L'article wikipedia a depuis été mis à jour et ne prétend plus pour correspondre à de multiples motifs de longueurs différentes en O (n).

Answer 1

Je ne suis pas sûr que ce soit la bonne réponse, mais de toute façon:
Alors que la construction la valeur de hachage, nous pouvons vérifier une correspondance dans l'ensemble des hash de chaîne. Aka, courant valeur de hachage. La fonction de hachage / code est généralement mis en œuvre en boucle et à l'intérieur de cette boucle, nous pouvons insérer notre recherche rapide.
Bien sûr, il faut choisir m avoir la longueur maximale de la chaîne de l'ensemble des chaînes.
Mise à jour: Un article de Wikipédia,

[...]
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
[...]

On calcule courant hachage dans les étapes de m. À chaque étape il y a un temporaire valeur de hachage que l'on peut rechercher dans l'ensemble de hash (O (1) la complexité). Tous les hash auront la même taille, soit 32 bits.

Mise à jour 2: un amorti (en moyenne) O (n) la complexité du temps?
Au-dessus, je dit que m doit avoir la longueur maximale de la chaîne. Il se avère que nous pouvons exploiter le contraire.
Avec hachant pour déplacer la recherche et substring un m fixe taille que nous pouvons atteindre O (n) complexité.
Si nous avons des chaînes de longueur variable, nous pouvons définir m à la longueur de chaîne minimum. De plus, dans l'ensemble de hash nous n'associons pas un hachage avec la chaîne entière mais avec les premiers m-caractères de celui-ci.
Maintenant, en cherchant le texte, nous vérifions si le hachage est en cours dans l'ensemble de hachage et nous examinons les chaînes associées pour un match.
Cette technique augmente les fausses alarmes, mais en moyenne, il a O (n) la complexité du temps.

Answer 2

Il est parce que les valeurs de hachage des sous-chaînes sont liées mathématiquement. Le calcul du hachage H (S, j) (le hachage des caractères à partir de la position j du string S ) tire O (m) temps sur une chaîne de longueur m . Mais une fois que vous avez, calcul H (S, j + 1) peut être fait en temps constant, parce que H (S, j + 1) peut être exprimé en fonction de H (S, j) .

O (m) + O (1) => O (m) , à savoir le temps linéaire.

Voici un lien où ceci est décrit plus en détail (voir par exemple la section « ce qui rend Rabin-Karp rapide? »)