[C++] Recherche d'1 motif

Fermé
arthix Messages postés 52 Date d'inscription lundi 30 juin 2003 Statut Membre Dernière intervention 31 août 2006 - 4 juil. 2003 à 09:39
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 - 8 juil. 2003 à 18:10
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 !
A voir également:

6 réponses

arthix Messages postés 52 Date d'inscription lundi 30 juin 2003 Statut Membre Dernière intervention 31 août 2006 5
4 juil. 2003 à 09:40
(en fait c pas des tableaux que j'utilise, mais des buffers ... on dira que c ma même chose)
0
tafiscobar Messages postés 1277 Date d'inscription jeudi 7 décembre 2000 Statut Contributeur Dernière intervention 26 février 2009 177
4 juil. 2003 à 15:06
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
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
7 juil. 2003 à 09:04
le quicksort pour faire une recherche ?!? Qu'est ce que tu racontes ?

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
arthix Messages postés 52 Date d'inscription lundi 30 juin 2003 Statut Membre Dernière intervention 31 août 2006 5
4 juil. 2003 à 15:10
ok merci tafiscobar & bon we bientôt !
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
7 juil. 2003 à 09:21
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 ?
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
tafiscobar Messages postés 1277 Date d'inscription jeudi 7 décembre 2000 Statut Contributeur Dernière intervention 26 février 2009 177
8 juil. 2003 à 15:23
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
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
8 juil. 2003 à 15:55
C'est toi qui devrait bien regarder mon post :-)

J'ai dit "algo de grep", pas grep :)

Je l'ai codé pour un mini-projet donné en 1ere année de DUT. Je sais donc qu'il est faisable et bien plus performant (on devait sortir un tableau suivant le nb de caractères à rechercher, le nombre de car. de la chaine dans laquelle rechercher etc.)

l'algo est évidemment plus complexe que la première chose qui vient à l'esprit, mais il n'est pas non plus très compliqué, loin de là.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
arthix Messages postés 52 Date d'inscription lundi 30 juin 2003 Statut Membre Dernière intervention 31 août 2006 5
8 juil. 2003 à 17:11
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+
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
8 juil. 2003 à 18:10
eh ben au boulot ! :-)
@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0