remplacement d'une sous chaine par une autre sous chaine C++

**mido1951** · 16/11/2015, 13h35

Envoyé par bacelar

Le plus naturel pour moi, créer une maps ordonnée de size_t pour la clé et int pour la valeur.
La clé (size_t) contient l'indice du début d'un remplacement déjà effectué et la clé donnera le décalage qu'il faudra ajouter pour récupérer l'ancien offset à partie de la nouvelle chaine.
Si la chaine de remplacement est plus longue que la chaine remplacée, la valeur sera positive de la différence de longueur entre le remplacé et le remplaçant, sinon elle sera négative.
Si le remplacé a la même longueur pas la peine d'ajouter un élément dans la maps.
Pour savoir de combien il faut faire dériver l'indice, il suffit d'ajouter toutes les valeurs dont la clé est inférieur à l'indice de départ du remplacement.

est-ce que tu peux développer?
c'est quoi une "maps"? c'est à dire trier mes intervalles du début à la fin puis à chaque remplacement je fais une mise à jour?

3 2881 ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT
8547 10456 CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA
4498 6926 GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC
6853 7847 ACGTTGGGCCACACACACACAGGGGGGGGGGTTTCTCGGGAAAAAAACCCCTTTTTTTTTTTTTTTTT
3678 4567 ......
2895 3684 ..........
2314 3242 ........
500 1503 ..........

la nouvelle devient (après trie):

3 2881 ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT
500 1503 .......... // puisque c'est inclut [3,2881] dans il va être éliminer
2314 3242 ........ // ici on un chevauchement donc le nouveau intervalle devient [2882,3242]
2895 3684 ..........// ici on un chevauchement donc le nouveau intervalle devient [3243,3684]
3678 4567 ...... // ici on un chevauchement donc le nouveau intervalle devient [3685,4567]
4498 6926 GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC // ici on un chevauchement donc le nouveau intervalle devient [4568,6926]
6853 7847 ACGTTGGGCCACACACACACAGGGGGGGGGGTTTCTCGGGAAAAAAACCCCTTTTTTTTTTTTTTTTT // ici on un chevauchement donc le nouveau intervalle devient [6927,7847]
8547 10456 CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA

mon idée est que je fais ça. Puis à chaque remplacement je fais une mise à jour de toutes les valeurs(debut-fin).
qu'est ce que vous pensez?

**white_tentacle** · 16/11/2015, 16h16

Quand tu fais une substitution à la position n, tu crées un décalage.

Ce décalage s’applique à tous les éléments à la position pos = n + longueur(chaîne à remplacer), et il vaut offset = longueur(chaîne de remplacement) - longueur(chaîne à remplacer).

L’idée est de stocker chacun de ces décalages dans un tableau associatif (map), avec pour clé l’indice de la position (pos), et pour valeur le décalage (offset).

Ensuite, pour chacun de tes indices, tu regardes s’il a fait l’objet de décalages, c’est à dire que tu vas parcourir la liste de ces décalages, et appliquer tous ceux (en partant du premier) dont la valeur est inférieure à la valeur actuelle de ton indice (que tu corriges à chaque fois du décalage).

Il y a juste un truc qui me chiffonne dans cette affaire, c’est si tu as des indices de position de départ qui se retrouvent au milieu de parties déjà substituées. Je ne comprends pas trop ce que c’est censé faire dans ce cas (d’un point de vue sémantique, je veux dire, ça me semble extrêmement étrange).

**mido1951** · 16/11/2015, 16h54

Envoyé par white_tentacle

Quand tu fais une substitution à la position n, tu crées un décalage.

Ce décalage s’applique à tous les éléments à la position pos = n + longueur(chaîne à remplacer), et il vaut offset = longueur(chaîne de remplacement) - longueur(chaîne à remplacer).

L’idée est de stocker chacun de ces décalages dans un tableau associatif (map), avec pour clé l’indice de la position (pos), et pour valeur le décalage (offset).

Ensuite, pour chacun de tes indices, tu regardes s’il a fait l’objet de décalages, c’est à dire que tu vas parcourir la liste de ces décalages, et appliquer tous ceux (en partant du premier) dont la valeur est inférieure à la valeur actuelle de ton indice (que tu corriges à chaque fois du décalage).

c'est mon idée que j'ai dejà expliquer dans mon message précédent. Mais je dois faire une mise à jour dans tous les positions car les positions vont changer dans la séquence SEQ.

Il y a juste un truc qui me chiffonne dans cette affaire, c’est si tu as des indices de position de départ qui se retrouvent au milieu de parties déjà substituées. Je ne comprends pas trop ce que c’est censé faire dans ce cas (d’un point de vue sémantique, je veux dire, ça me semble extrêmement étrange).

tu veux dire qu'il y a un chevauchement. Pour les chevauchements, je dois éliminer les parties qui se chevauchement.
Alors, votre avis?

**white_tentacle** · 16/11/2015, 17h35

Envoyé par mido1951

c'est mon idée que j'ai dejà expliquer dans mon message précédent. Mais je dois faire une mise à jour dans tous les positions car les positions vont changer dans la séquence SEQ.

Non, pas de mise à jour des décalages car la « mise à jour » se fait lors de l’application, car tu appliques successivement tous les décalages.

Je n’ai pas le temps tout de suite, je déroulerai un exemple plus tard si ce n’est pas clair.

**bacelar** · 16/11/2015, 18h31

La solution de @stendhal666 ne fonctionne pas parce que l'indice de démarrage du remplacement n'est pas strictement croissant.
@white_tentacle a parfaitement expliqué la solution, de manière bien plus simple que je ne l'aurais fait.

Mais je dois faire une mise à jour dans tous les positions car les positions vont changer dans la séquence SEQ.

Bin non, si tu a un décalage qui vient en début de chaine, il y aura la valeur du décalage dans la map à un indice faible.
Et lors du calcul du décalage sur le nouveau remplacement, ce décalage sera ajouter systématiquement si l'indice de démarrage du nouveau remplacement est supérieur à l'indice/clé de la map (indice de démarrage du remplacement ayant provoqué ce décalage).

3 2881 ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT

"ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT" => 60 de long
on ajoute dans la map {3,-2821}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.

8547 10456 CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA

On calcul le vrai indice de départ :
8547 + (-2821) = 5726
On remplace donc la chaine commençant à 5726 de longueur 10456 par "CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA" (62 de long)
10456 - 62 = 10394
on ajoute dans la map {8547,-10394}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.
et si un remplacement commence après l'indice 8547, on soustrait 10394 à l'indice de départ.

4498 6926 GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC

On calcul le vrai indice de départ :
4498 + (-2821) = 1677
On n'utilise pas l'offset en "8547" car il est supérieur à 4498.
On remplace donc la chaine commençant à 1677 de longueur 6926 par "GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC" (61 de long)
on ajoute dans la map {4498,(-6926+61)}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.
si un remplacement commence après l'indice 4498, on soustrait 6865 à l'indice de départ.
et si un remplacement commence après l'indice 8547, on soustrait 10394 à l'indice de départ.

etc....

Pour les chevauchements, je dois éliminer les parties qui se chevauchement.

Bon, on pourra pas vous faire cette transformation à votre place, surtout que vous ne dite rien des règles qui président à cette "élimination".
S'il n'y plus de chevauchement, l'ordre des remplacements n'est plus contraignant, on peut donc réordonner ces remplacements et donc ordonner correctement ces remplacement pour que l'algorithme de @stendhal666 fonctionne.

**mido1951** · 17/11/2015, 01h55

Envoyé par bacelar

La solution de @stendhal666 ne fonctionne pas parce que l'indice de démarrage du remplacement n'est pas strictement croissant.
@white_tentacle a parfaitement expliqué la solution, de manière bien plus simple que je ne l'aurais fait.

Bin non, si tu a un décalage qui vient en début de chaine, il y aura la valeur du décalage dans la map à un indice faible.
Et lors du calcul du décalage sur le nouveau remplacement, ce décalage sera ajouter systématiquement si l'indice de démarrage du nouveau remplacement est supérieur à l'indice/clé de la map (indice de démarrage du remplacement ayant provoqué ce décalage).

"ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT" => 60 de long
on ajoute dans la map {3,-2821}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.

On calcul le vrai indice de départ :
8547 + (-2821) = 5726
On remplace donc la chaine commençant à 5726 de longueur 10456 par "CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA" (62 de long)
10456 - 62 = 10394
on ajoute dans la map {8547,-10394}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.
et si un remplacement commence après l'indice 8547, on soustrait 10394 à l'indice de départ.

On calcul le vrai indice de départ :
4498 + (-2821) = 1677
On n'utilise pas l'offset en "8547" car il est supérieur à 4498.
On remplace donc la chaine commençant à 1677 de longueur 6926 par "GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC" (61 de long)
on ajoute dans la map {4498,(-6926+61)}
Donc si un remplacement commence après l'indice 3, on soustrait 2821 à l'indice de départ.
si un remplacement commence après l'indice 4498, on soustrait 6865 à l'indice de départ.
et si un remplacement commence après l'indice 8547, on soustrait 10394 à l'indice de départ.

etc....

Bon, on pourra pas vous faire cette transformation à votre place, surtout que vous ne dite rien des règles qui président à cette "élimination".
S'il n'y plus de chevauchement, l'ordre des remplacements n'est plus contraignant, on peut donc réordonner ces remplacements et donc ordonner correctement ces remplacement pour que l'algorithme de @stendhal666 fonctionne.

la deuxième colonne n'est pas la longueur de la chaine C (de remplacement). c'est la position de fin dans SEQ afin de concaténer le reste après le remplacement.
et Oui pour les parties qui se chevauchent comment faire.
c'est pour cette raison que j'ai voulu modifier toutes les positions.

**white_tentacle** · 17/11/2015, 09h00

Envoyé par mido1951

Oui pour les parties qui se chevauchent comment faire ?

En fait, il y a une petite erreur : il ne faut pas une map, mais une liste ordonnée (l’ordre des substitutions est important).
Je prends un exemple :

chaîne de départ : abcdefghijklmnopqrstuvwxyzEt les substitutions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
4 12 aaaaaaaaaaaaaa
16 18 bbbbbb
7 14 ccc

J’applique la première substitution, ça me donne abcd aaaaaaaaaaaaaa mnopqrstuvwxyz (les espaces sont en plus, pour montrer ce qui a changé).

Je stocke dans ma liste de décalage : 12 (indice de fin), 6 (14 - 8), 14 = longueur nouvelle chaîne, 8 = longueur ancienne chaîne
J’applique la transformation suivante :
16 > 12, donc j’applique le décalage à mon indice, je substitue donc à la position 20, et jusqu’à la position 22 (même remarque)
Ce qui me donne : abcdaaaaaaaaaaaaaamnop bbbbbb stuvwxyz.
Je rajoute à ma liste de décalages 22 (indice de fin corrigé), 4.

Elle contient donc : (12, 6) (22, 4). Elle me permet de corriger la position d’un élément initialement dans la chaîne. Par exemple, « x » était à la position 24. Maintenant, il est à la position 34. « m », qui était à la position 13, se trouve à la position 19 (on applique le premier décalage, pas le second).

Maintenant, on cherche à appliquer la troisième transformation. L’indice de départ est 7. Or, 7, au départ, c’était « g ». Ceci est en plein dans une chaîne qui a été substituée. Donc si on applique « bêtement », voilà ce qu’il se passe :
Je corrige mon indice de départ. Rien à faire, car il l’indice de départ est inférieur au premier décalage, donc 7.
Je corrige l’indice d’arrivée. Il vaut 14, c’est supérieur à 12, donc je corrige de 6. Ça me donne 20.
J’applique la substitution. Ça me donne abcdaaa ccc op bbbbbb stuvwxyzEt je stocke dans ma liste, qui vaut donc (12, 6) (22, 4) (20, -10) (-10 car j’ai substitué une chaîne de longueur 13 par une chaîne de longueur 3).

Si je vérifie, l’indice de « o » (au départ, 15), vaut maintenant 15 + 6 = 21, < 22 donc on n’applique pas la deuxième transformation, > 20, donc = 21 - 10 = 11, ce qui est correspond. Si je cherche « x », il vaut 24 + 6 = 30, > 22 donc 34, > 20 donc = 24. Là encore je retrouve mes petits.

Avec cette méthode, à minima, je suis cohérent et capable de retrouver, à partir de l’indice initial d’un élément, sa position dans la nouvelle chaîne, à condition qu’il s’y trouve toujours. En revanche, pour les éléments qui ont disparu, je ne sais pas du tout ce qui doit être pris en compte. En effet, toujours sur notre exemple, je cherche la position de « m ». Ça me donne :
13 > 12 -> 19. Et à la position 19, j’ai « s ». Fondamentalement, « m » n’est plus là, chercher sa position n’a pas de sens. Il y a pour moi un gros problème de sémantique à ce niveau : qu’est-ce qu’on cherche à faire. Là je n’ai pas la connaissance suffisante du problème initial pour répondre.

**mido1951** · 15/12/2015, 14h30

est-ce qu'il y a l'équivalent de la fonction replace() en C???
Merci

**bacelar** · 15/12/2015, 14h50

De quelle "fonction replace() en C???" parlez-vous ???

**stendhal666** · 15/12/2015, 16h54

A vue de nez la méthode Java de la class String, qui remplace une sous-chaîne par une autre?

**stendhal666** · 15/12/2015, 17h04

La réponse est non, au fait, du moins dans la librairie standard.

Si la sous-chaîne de remplacement est de la même taille que la sous-chaîne d'origine, c'est assez aisé à faire en combinant les fonctions standard:
- strstr, pour trouver l'emplacement de la sous-chaîne à remplacer
- strncpy, pour écrire par dessus la chaîne de remplacement.

Sinon, c'est comme d'habitude en C, il faut tout faire soi-même

1) allouer de la mémoire pour la chaîne après modification (longueur originale + différence de longueur entre sous-chaîne d'origine et de remplacement, sans oublier le caractère null, hein?)
2) copier le début de la chaîne dans cette mémoire, par ex: strncpy(outstr, instr, strstr(instr, oldsubstr) - instr);
3) copier la nouvelle sous-chaîne: même principe
4) copier la fin de la chaîne: même principe
5) recommencer l'opération tant que l'ancienne sous-chaîne est présente dans la chaîne modifiée.

**Bousk** · 15/12/2015, 17h31

En même temps on est sur le forum C++.
Et je viens de voir que j'avais proposé une fonction Replace tout à fait fonctionnelle dès les premières réponses.
Si vous avez quelque chose contre elle, faîtes-le savoir

Parce que là on dirait franchement de l'absence de recherche... et de lecture des réponses faîtes à son propre sujet.

remplacement d'une sous chaine par une autre sous chaine C++

C++

Discussions similaires

Partager

Partager