[C++] Recherche d'1 motif Fermé

Question

Salut !Recherche d'idées ingénieuses : j'ai deux tableaux, un qui peut être relativement énorme, et un autre contenant un motif à rechercher dans le premier tableau.Quelle méthode utiliseriez vous pour rechercher le plus rapidement possible, et en utilisant le - de ressources possibles aussi, pour rechercher combien de fois on a les fameux motif dans le premier tableu ?Thanks !

arthix · Answer

(en fait c pas des tableaux que j'utilise, mais des buffers ... on dira que c ma même chose)

tafiscobar · Answer

il ya des algo de recheche ds 1 tableau, la complexite allant de n² a n, tu as par ex le quicksort(nlog(n)) , l'algo combinaison (n) , n etant la taille du tableau.tafiscobar

arthix · Answer

ok merci tafiscobar & bon we bientôt !

batmat · Answer

Pour effectuer cette recherche, il faut utiliser l'algo de grep. @++Vous hésitez entre Linux et Windows ?Vous voulez dépenser du temps ou de l'argent ?

tafiscobar · Answer

batmat, reagrdes bien son poste, il a un tableau, il n'a pas de listes du genre renvoye par un pipe du genre : ls -l | grep "toto".bien sur que le quicksort fait un tri, desole arthix pour cette erreur, je voulais dire recherche dichotomique, merci batmat, now si grep est une fct de biblio qui le fait tant mieux.tafiscobar

arthix · Answer

Salut à tous & merci pour vous réponses !Un élément important que je n'avais pas cité parceque je voyais mon pb d'un oeil différent, c'est qu'après chaque motif trouvé dans la source de données, il faut insérer une autre quantité de données fixe. Explication, je ne me sens pas clair : - on recherche le motif  "1 2"- on veut insérer "3 4" après ce motif- la chaine d'entrée est "1 3 5 1 2 5 1 2 9"en sortie, on aura donc "1 3 5 1 2 3 4 5 1 2 3 4 9"Tout le problème réside en fait dans l'allocation de mémoire...Pour effectuer cette opération, malgrès la taille qui peut parfois être TRES importante du tableau "source, on va retenir l'indice du début du motif dans un nveau tableau, puis dans un second temps, on va générer le nouveau buffer de sortie...A priori on peut bourriner sur la ram donc tout ca bien ...merci & A+

[C++] Recherche d'1 motif

6 réponses

Discussions similaires