M1102-TD6 Exercie4 Corrigé

fonction TrouveCarDansStr (Caract : in caractere,
Chaine : in string,
Debut  : in entier_naturel) renvoie entier_naturel
debut
declarer i : entier_naturel;
i <- Debut;
tant_que (i < taille(Chaine) ET_ALORS Caract ne_vaut_pas Chaine [i])
faire
i <- i +1;
ffaire
renvoie i;
fin

fonction FindSubInStr (SsChaine : in string, Chaine : in string, Debut : in entier_naturel) renvoie entier_naturel
debut

//on se demande s'il y a la place pour faire la recherche
si (taille (SsChaine) + Debut >= taille (Chaine)) renvoie taille (Chaine);

//peut-on accéder à l'élément en position 0 de la sous-chaine? non => on sort
si (taille (SsChaine) vaut 0) renvoie taille (Chaine);

declarer i : entier_naturel;
i <- Debut;

declarer j : entier_naturel;
j <- 0;

boucle
//on cherche la première occurence de SsChaine [0] dans Chaine à partir de la position i
i <- TrouveCarDansStr (SsChaine [0], Chaine, i);

//cas 0: si la recherche a échouée (on ne peut pas trouver le sous-motif), alors on sort
si (i vaut taille (Chaine)) sortie;

//si on ne sort pas, l'assertion SsChaine [0] vaut Chaine [i] est vraie
//cas 1 : on se demande alors si on peut placer la sous-chaine entre la position i et la fin de la chaine sans faire de
//débordement de case. Si ce n'est pas le cas, on sort de la boucle
si (i + taille (SsChaine) > taille (Chaine)) sortie;

//cas 2: on peut lancer la recherche
//on parcourt donc le reste de la sous-chaine
j <- 1;
tant_que (j < taille (SsChaine) ET_ALORS Chaine [i + j] vaut SsChaine [j])
faire
j <- j +1;
ffaire

//si on a atteint la fin de la sous-chaine, on sort de la boucle
si (j vaut taille (SsChaine)) sortie;

//si on ne sort pas, on prépare la prochaine recherche
i <- i + 1;
fboucle

si (j ne_vaut_pas taille (SsChaine))
i <- taille (Chaine);
fsi
renvoie i;
fin
//astuce : même si le test ligne 34 (cas 0) est juste, il est couvert par celui en ligne 39 (cas 1)
//on pourrait donc s'en passer :)

algorithme TestFindSubInStr
debut
boucle
// Saisie

declarer LigneLue : string;
afficher ("Entrer une string (ligne vide pour sortir) : ");
saisir (LigneLue);

si (taille (LigneLue) vaut 0) sortie;

// La ligne traitée est non vide

declarer SousChaine : string;
boucle
afficher ("Entrer la sous-chaine cherchee  : ");
saisir (SousChaine);
si (taille (SousChaine) ne_vaut_pas 0) sortie;
fboucle

declarer Pos : entier_naturel;
afficher ("Entrer la position à partir de laquelle vous souhaitez faire la recherche : ");
saisir (Pos);

declarer PosCherchee : entier_naturel;
PosCherchee <- FindSubInStr (SousChaine, LigneLue, Pos);

// Affichage
si (PosCherchee < taille (LigneLue))
afficher ("On trouve  le motif \"", SousChaine, "\" dans la chaine ", LigneLue);
afficher (" pour la première fois à partir de la position ", Pos, " en position ", PosCherchee);
sinon
afficher ("On ne trouve pas le motif \"", SousChaine, "\" dans la chaine ", LigneLue, " a partir de la position ", Pos);
fsi
ligne_suivante;
fboucle
fin