Previous Up Next

Chapitre 5  Des programmes tres simples sur les chaînes de caractères

5.1  Compter un nombre d’occurences

5.1.1  Nombre d’occurences d’une lettre

On parcourt la chaîne S et on augmente le compteur n de 1 lorsqu’il y a égalité avec le caractère c.

Occurc(c,S):={
  local n,d,j;
  d:=dim(S)-1;
  n:=0;
  pour j de 0 jusque d faire
    si c==S[j]  alors n:=n+1 fsi;
  fpour;
  retourne n;
}:;

On tape :
Occurc("e","occurrences")
On obtient : 2

5.1.2  Nombre d’occurences d’une sous-chaîne

Il faut comparer à chaque étape la sous-chaîne ch avec un morceau de la chaîne S qui a même longueur.
On va utiliser mid(S,j,k) qui renvoie la sous chaîne de S de longueur k qui commence à l’indice j ou mid(S,j) qui renvoie la sous-chaîne fin de S commençant à l’indice j.
Remarque À la place de mid(S,j,k) on peut aussi utiliser S[j..j+k-1] (on met les indices de début et de fin de la sous-chaîne) et à la place de mid(S,j) on peut aussi utiliser S[j..dim(S)-1].
On considère que dans "aaa" on voit une seule sous-chaîne "aa".

Occurch(ch,S):={
  local n,d,j,k;
  d:=dim(S)-1;
  k:=dim(ch);
  n:=0;
  j:=0;
  tantque j<= d-k+1 faire
    si ch==mid(S,j,k)  alors 
      n:=n+1; 
      j:=j+k; 
      sinon
        j:=j+1
    fsi;
  fpour;
  retourne n;
}:;

On tape :
Occurch("e","occurrences")
On obtient : 2
On tape :
Occurch("az","aaazaaazaaaz")
On obtient : 3
On tape :
Occurch("aa","aaazaaazaaaz")
On obtient : 3

5.2  Supprimer une lettre et sous-chaîne

5.2.1  Supprimer une lettre

On parcourt la chaîne S lorsqu’il y a égalité avec le caractère c il faudra supprimer ce caractère en faisant une concaténation entre ce qu’il y a avant c (si c est d’indice j c’est mid(S,0,j) car ce qu’il y a avant c est de longueur j) et ce qu’il y a après c (mid(S,j+1)). On met alors à jour la longueur de S.

Supprimec(c,S):={
  local d,j;
  d:=dim(S)-1;
  j:=0;
  tantque j<=d faire
    si c==S[j]  alors 
      S:=mid(S,0,j)+mid(S,j+1);
      d:=d-1;
    sinon
      j:=j+1
    fsi;
  ftantque;
  retourne S;
}:;

On tape :
Supprimec("e","occurrences")
On obtient : "occurrncs"

5.2.2  Supprimer une sous-chaîne

On parcourt la chaîne s lorsqu’il y a égalité avec la sous-chaîne ch il faudra supprimer cette sous-chaîne en faisant une concaténation entre ce qu’il y a avant ch et ce qu’il y a après ch. On met alors à jour la longueur de S.

Supprimech(ch,S):={
  local k,d,j;
  d:=dim(S)-1;
  k:=dim(ch);
  j:=0;
  tantque j<=d faire
    si ch==mid(S,j,k)  alors 
      S:=mid(S,0,j)+mid(S,j+k);
      d:=d-k;
    sinon
      j:=j+1
    fsi;
  ftantque;
  retourne S;
}:;

On tape :
Supprimech("e","occurrences")
On obtient : "occurrncs"
On tape :
Supprimech("az","azerazerazaz")
On obtient : "erer"
On tape :
Supprimesch("aa","aaazaaazaaaz")
On obtient : "azazaz"

5.3  Remplacer une lettre ou une sous-chaîne par une autre chaîne

5.3.1  Remplacer une lettre par une autre lettre

Pour remplacer le caractére a par b dans S, on parcourt S et quand on trouve le caractére a on change ce caractére.

Remplaceab(a,b,S):={
local d,j;
  d:=dim(S)-1;
  j:=0;
  tantque j<=d faire
    si a==S[j]  alors 
      S:=mid(S,0,j)+b+mid(S,j+1);
    sinon
      j:=j+1
    fsi;
  ftantque;
  retourne S;
}:;

On tape :
Remplaceab("a","e","azerazerazaz")
On obtient : "ezerezerezez"

5.3.2  Remplacer une sous-chaîne par une autre

Pour remplacer la sous-chaîne cha par la sous-chaîne chb dans S, on parcourt S et quand on trouve la sous-chaîne cha. on fait une concaténation entre ce qu’il y a avant cha, la sous-chaîne chb et ce qu’il y a après cha. On met alors à jour la longueur de S.

Remplacechab(cha,chb,S):={
local ka,kb,d,j;
  d:=dim(S)-1;
  ka:=dim(cha);
  kb:=dim(chb);
  j:=0;
  tantque j<=d faire
    si cha==mid(S,j,ka)  alors 
      S:=mid(S,0,j)+chb+mid(S,j+ka);
      d:=d-ka+kb;
    sinon
      j:=j+1
    fsi;
  ftantque;
  retourne S;
}:;

On tape :
Remplacechab("a","e","azerazerazaz")
On obtient : "ezerezerezez"
On tape :
Remplacechab("az","bcd","azerazerazaz")
On obtient : "bcderbcderbcdbcd"


Previous Up Next