Algorithme de Rabin-Karp

Marie6 · May 2002

Bonjour,

Comment expliquer que l'algorithme de Rabin-Karp a, en moyenne, une complexité de O(m+n) ?

Merci d'avance
Marie

Jean Bureau · May 2002

<HTML>c'est quoi l'algorithme de Rabin-Karp ?

Marie6 · May 2002

<HTML>C'est un algorithme de recherche de motifs. Dans l'algorithme naif, chaque étape de comparaison entre deux décalages du motif nécessite un nombre de comparaisons égal à la longueur du motif. Karp et Rabin ont proposé une méthode de hachage permettant d'éviter de faire trop de comparaisons de lettres. Soit h la fonction de hachage qui transforme une chaîne en un entier. Si la valeur de la fonction de hachage du motif recherché est différente de la partie du texte considéré, alors le motif ne peut apparaître à cette place. En revanche, si les deux valeurs de hachage sont égales, il faut comparer un à un les caractères pour savoir si on a bien une occurrence du motif.

La fonction de hachage ramène donc la comparaison de m lettres à celle de deux entiers. Karp et Rabin ont utilisé la fonction h(x)=x mod q pour un nombre premier q suffisamment grand.

khadidja0 · December 2011

bjr
comment les fonctions de hashage font les calcules????? c koi la methode??? merci

gerard0 · December 2011

Bonjour Khadidja.

1) On n'accepte pas le langage SMS en maths, donc ici (Il faut être clair).
2) Poser une question dans le sujet d'un autre est impoli. Tu pouvais créer aussi facilement un nouveau fil.
3) Une recherche avec un moteur de recherche t'aurait déjà donné une réponse.

khadidja1 · January 2012

Bonjour Monsieur gerard, je vous remercie pour votre réponse
1- je pense pas que mon langage est un langage de SMS

et ma question était tres claire c'est pas ma faute si vous l'avez pas compri

2- L'Algorithme de Rabin-Karp utilise les fonctions de hashage, donc jai pas posé une question hors sujet

3- Sache que jai cherché et javais besoin un coup de main pour éclairssir les choses dans ma tete c tout

et c'est vraiment impoli de repondre sur une question de cette maniere Merci

Eric Chopin · January 2012

Khadidja,

Commence donc par lire ceci:

http://www.les-mathematiques.net/phorum/read.php?2,346997,346997#msg-346997

Comme Gerard le rappelle, sur ce forum on attend de ceux qui postent des messages
qu'ils l'écrivent en français compréhensible, et s'il est évident qu'on tolère des fautes d'orthographes ponctuelles,
un message illisible ou écrit avec trop de langage SMS à l'intérieur pourra être supprimé, parce que justement
nous considérons que celui qui écrit de cette façon sur le forum est impoli vis à vis de ceux qui lisent le forum.
Merci d'en tenir compte dans tes prochains messages.

Eric

gerard0 · January 2012

khadidja a écrit:

bjr
c koi

Si ce n'est pas du langage SMS, je suis le pape !

et javais besoin un coup de main pour éclairssir les choses dans ma tete c tout

Encore du SMS : "c" pour "c'est". Et après avoir dit "je pense pas que mon langage est un langage de SMS". Donc Khadidja ne sait pas ce qu'il écrit

Et pour éclaircir des choses dans sa tête, on aurait eu bien besoin de savoir ce qu'il sait, ce qu'il a compris et ce qui ne passe pas. mais

comment les fonctions de hashage font les calcules?????

est tellement plus facile que de commencer par expliquer où on en est, ce qu'on sait et ce qui pose problème. Après tout, les "impolis" qui répondent sur un forum feront bien le travail à ma place ...