Discussion :

[mido1951]

bonjour,
Je veux faire un remplacement d'une sous chaine par une autre souschaine à plusieurs emplacements.
voici mon code:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
 
using namespace std;
 
int main(void)
{
    string s = "abcerfg";
 
    s.replace(3, 2, "HHHHHHH");
    s.replace(5,1,"AAAAA");
 
    cout << s << endl;
    return 0;
}

ici je veux remplacer "er" par "HHHHHHH".
et je veux remplacer "f" par "AAAAA"
pour avoir un resultat "abHHHHHHHrAAAAAg"

mais voici le resultat par le prog: "abcHHAAAAHHHHHfg"
est-ce que vous avez une solution?
merci

[dragonjoker59]

Ben une fois que tu as effectué ton premier remplacement, les indices ont changé, et donc le 5 ne correspond plus à f, mais à un 'A' (parmi ceux que tu viens d'insérer)

[bacelar]

Et les indices commencent à 0 pas à 1.

[dragonjoker59]

Et les indices commencent à 0 pas à 1.

Tout à fait, et son premier indice (3) correspond bien au 'e', et son second (5) correspond bien à la position initiale de 'f'. (ou il a édité son post depuis ta remarque?)

[mido1951]

est-ce qu'il y a une solution pour garder les indices?

[stendhal666]

Oui!

La solution la plus simple est de commencer par la correction qui est le plus loin dans la chaîne, comme ça les indices antérieurs ne sont pas faussés.

La solution la plus robuste est de rechercher dans la chaîne l'endroit où commence la chaîne que tu veux remplacer et de faire ton replace ensuite. Il y a la fonction find pour cela:

Code :

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

1
2
3
4
5
6
7
8
#include <string>
 
int main() {
 
  std::string s = "abcdefghij";
  s.replace(s.find("cde"), 3, "AHAHAHAH");
 
}

[Bousk]

Le plus simple je sais pas, ça reste du bricolage. Simple sur un cas trivial comme ça, mais vite dépassé.
Le mieux par contre serait de faire un chouilla d'algorithmique pour y parvenir. Rien de bien sorcier d'ailleurs.
Un truc comme

Code :

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

1
2
3
4
5
6
7
8
9
10
11
std::string Replace(std::string in, const std::string& toReplace, const std::string& replacement)
{
  for( size_t i = 0, p = in.find(toReplace, i);
        p != std::string::npos;
        i = p + replacement.length(), p = in.find(toReplace, i)
      )
  {
    in.replace(p, toReplace.length(), replacement);
  }
  return in;
}

Le seul "trick" c'est de bien bouger le i pour ne pas finir en boucle infinie avec un appel comme Replace("toto", "to", "toto").

[bacelar]

Tout à fait, et son premier indice (3) correspond bien au 'e', et son second (5) correspond bien à la position initiale de 'f'. (ou il a édité son post depuis ta remarque?)

ici je veux remplacer "er" par "HHHHHHH".
et je veux remplacer "f" par "AAAAA"
pour avoir un resultat "abHHHHHHHrAAAAAg"

mais voici le resultat par le prog: "abcHHAAAAHHHHHfg"
est-ce que vous avez une solution?
merci

Code :

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

    s.replace(3, 2, "HHHHHHH");

Avec ce machin il n'aura jamais "abHHHHHHHrAAAAAg" car ça commencera toujours par "abc..."

[mido1951]

Oui!

La solution la plus simple est de commencer par la correction qui est le plus loin dans la chaîne, comme ça les indices antérieurs ne sont pas faussés.

La solution la plus robuste est de rechercher dans la chaîne l'endroit où commence la chaîne que tu veux remplacer et de faire ton replace ensuite. Il y a la fonction find pour cela:

Code :

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

1
2
3
4
5
6
7
8
#include <string>
 
int main() {
 
  std::string s = "abcdefghij";
  s.replace(s.find("cde"), 3, "AHAHAHAH");
 
}

bon c'est dans le cas oü les séquences à modifier sont distinctes mais si j'ai des séqences ADN ça marche pas la fonction s.find("cde")!!.
en plus moi j'ai plusieurs remplacements pas un seul donc le problème est un peu compliqué.

[dragonjoker59]

Avec ce machin il n'aura jamais "abHHHHHHHrAAAAAg" car ça commencera toujours par "abc..."

Ah effectivement, c'était donc là que se situait ta remarque, désolé.

[bacelar]

j'ai plusieurs remplacements pas un seul donc le problème est un peu compliqué.

Donnes nous le vrai problème, là, tu obscurcie le truc.

[mido1951]

j'ai un alignement de deux séquences et voici le fichier de sortie.
3 2881 ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT
8547 10456 CTTGCTTAACCGTTGGCCCGGGGGGGGGAAACGTGTGTGTGTAAAACCCCCCCTGGGAAAAA
4498 6926 GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC
6853 7847 ACGTTGGGCCACACACACACAGGGGGGGGGGTTTCTCGGGAAAAAAACCCCTTTTTTTTTTTTTTTTT
3678 4567 ......
2895 3684 ..........
2314 3242 ........
500 1503 ..........

la première et la deuxième colonne c'est la position du début et de fin d'alignement dans la séquence SEQ.
et la troisième colonne c'est la partie de l'alignement d'une séquence C avec SEQ.
Je veux faire une modification à partir de la position debut jusqu'à la fin de la séquence SEQ en mettant la séquence de la troisième colonne.
c'est à dire dans la position de 3 à 2881 je mettre "ATTTAAGTGCCTGGGCCCCTTTGGAACCGTTTAAACCGTTGTGTGGTGTTGAAATTTTTT". (par exemple)
est-ce que vous avez une solution?
Merci

[bacelar]

Vos intervalles ne sont pas ordonnées et se chevauchent, le résultat attendu est donc ambiguë.

4498 6926 GTGGGTTCCCAAAACGTTGGGCCACACACACACAGGGGGGGGGGTTTGGGGGGCCCCACCC
6853 7847 ACGTTGGGCCACACACACACAGGGGGGGGGGTTTCTCGGGAAAAAAACCCCTTTTTTTTTTTTTTTTT

Ce 6853, c'est l'indice dans la séquence de base avant transformation ou après avoir appliqué les différentes modifications ?
Je fais l'assertion que la taille de la séquence de remplacement n'est pas forcement de la même longueur que la séquence à remplacer.
La chaine a donc une longueur variable, on n'est OK ?

[mido1951]

Vos intervalles ne sont pas ordonnées et se chevauchent, le résultat attendu est donc ambiguë.

oui les intervalles ne sont pas ordonnées et se chevauchent.

Ce 6853, c'est l'indice dans la séquence de base avant transformation ou après avoir appliqué les différentes modifications ?

c'est l'indice dans la séquence de base sans transformation donc après la première transformation ces positions vont changer. Et si on essai une deuxième modification ils vont encore changer.

Je fais l'assertion que la taille de la séquence de remplacement n'est pas forcement de la même longueur que la séquence à remplacer.
La chaine a donc une longueur variable, on n'est OK ?

oui exactement ils n'ont pas la même taille. la chaine est de longueur variable.
c'est le problème généralement donc comment faire? j'ai réfléchit sur plusieurs approches mais ils ne marchent pas.
Merci

[jo_link_noir]

Que cela donne t-il avec un exemple simplifié ?

abcdef

0 2 x
1 3 y

xydef ?

[mido1951]

Que cela donne t-il avec un exemple simplifié ?
abcdef

0 2 x
1 3 y

xydef ?

ici, l'exemple est un peu complexe et pas simplifié.
voici un exemple simplifier.
la sequence SEQ: abcdefghijklmnopq
1 3 AAAAA
5 7 XXXXXXX
6 7 XXXX --> inclut dans [5,7] donc on va pas le mettre.
6 10 TTTTTT --> se chevauche avec [5,7] donc les positions changent en [8,10].

SEQ devient: aAAAAdeXXXXXXXTTTmnopq.
voila.

[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.

[stendhal666]

la sequence SEQ: abcdefghijklmnopq
1 3 AAAAA
5 7 XXXXXXX
6 7 XXXX --> inclut dans [5,7] donc on va pas le mettre.
6 10 TTTTTT --> se chevauche avec [5,7] donc les positions changent en [8,10].

SEQ devient: aAAAAdeXXXXXXXTTTmnopq.
voila.

Sans même passer par une structure de données complexe, il me semble qu'en calculant un offset à chaque changement tu devrais être tranquille:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int sp_replace(const std::string& in, int pos, int off, int len, const std::string& subst) {
  int o = subst.length() - len;
  in.replace(pos + off, len, subst);
  return o;
}
 
int main() {
 
  std::string s = ... // SEQ 
  int offset = 0;
 
  while ( /* il reste des modifs à faire */) {
    int p, l;
    std::string subst;
    /* parse tes modifs pour remplir p, l, subst */
    offset += sp_replace(s, p, offset, l, subst);
  }
}

du coup ça donnerait:

la sequence SEQ: abcdefghijklmnopq
1 3 AAAAA // offset = 2
5 7 XXXXXXX // offset = 2
6 7 XXXX --> inclut dans [5,7] donc on va pas le mettre. // optimisation à faire quand le programme marchera: premature optimization is the root of all evil!
6 10 TTTTTT --> se chevauche avec [5,7] donc les positions changent en [8,10]. // 6 + offset = 8, on est bons

SEQ devient: aAAAAdeXXXXXXXTTTmnopq. // en revanche je ne comprends pas pourquoi il ne reste que 3 des 6 T?
voila.

[Médinoc]

Ah, je n'avais pas vu que c'était un multipost. L'autre thread est ici: problème idée de programmation

[mido1951]

Sans même passer par une structure de données complexe, il me semble qu'en calculant un offset à chaque changement tu devrais être tranquille:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int sp_replace(const std::string& in, int pos, int off, int len, const std::string& subst) {
  int o = subst.length() - len;
  in.replace(pos + off, len, subst);
  return o;
}
 
int main() {
 
  std::string s = ... // SEQ 
  int offset = 0;
 
  while ( /* il reste des modifs à faire */) {
    int p, l;
    std::string subst;
    /* parse tes modifs pour remplir p, l, subst */
    offset += sp_replace(s, p, offset, l, subst);
  }
}

du coup ça donnerait:

Bon ta solution marche pour cet exemple mais quand on a :

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

je pense pas que ça marche.
en plus o = subst.length() - len retourne toujours une valeur négative puisque SEQ.len() >> Substr.len().

6 10 TTTTTT --> se chevauche avec [5,7] donc les positions changent en [8,10]. // 6 + offset = 8, on est bons

SEQ devient: aAAAAdeXXXXXXXTTTmnopq. // en revanche je ne comprends pas pourquoi il ne reste que 3 des 6 T?
voila.

car on pris à partir de l'intervalle [8,10] donc la chaine c=TTTTTT on va prendre que les trois derniers caractères.
donc votre solution ne marche pas pour un exemple comme ça.