Algorithme de Rabin-Karp
dans Les-mathématiques
Bonjour,
Comment expliquer que l'algorithme de Rabin-Karp a, en moyenne, une complexité de O(m+n) ?
Merci d'avance
Marie
Comment expliquer que l'algorithme de Rabin-Karp a, en moyenne, une complexité de O(m+n) ?
Merci d'avance
Marie
Réponses
-
<HTML>c'est quoi l'algorithme de Rabin-Karp ?
-
<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. -
bjr
comment les fonctions de hashage font les calcules????? c koi la methode??? merci -
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. -
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 -
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 -
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. maiscomment les fonctions de hashage font les calcules?????c'est vraiment impoli de repondre sur une question de cette maniere
Et les smiley ne changent rien à l'affaire.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres