Une chaîne dans une autre ! en C.

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour je viens vous demander de l'aide car j'ai un petit problème avec l'un de mes programmes en C.

Je dois déterminer si une chaîne de caractère se trouve dans une autre sans utiliser d'autres fonctions que strlen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>

int main(void)
{
    char src[256] = {};
    char facteur[256] = {};
    int compteur = 0;
    unsigned i;

    printf("Saisir le premier mot: ");
    scanf("%s", &src);
    printf("Saisir le deuxiéme mot: ");
    scanf("%s", &facteur);
    int longueur = strlen(src);
    int longueurFacteur = strlen(facteur);
    /* boucle for juqu'à la fin du mot src.
    Le but étant de vérifier que le mot facteur est un facteur de src.*/
    for(i=0 ; i<longueur ; i++){
        //Si la lettre du mot facteur est égale à la lettre du mot src, on incrémente i  
        if(facteur[i] == src[j]){
            compteur++;
        /*l faut ensuite vérifier si la valeur de la variable compteur est égale à la longueur du mot facteur.*/        
        if(compteur == longueurFacteur)
            printf("Le mot %s est bien un mot facteur de %s \n", facteur, src); 
        }

    }

    return 0;
}

Par exemple, dans le mot polycopie, le mot poly le mot copi sont des chaînes qui sont présents dans polycopie.

Alors avec mon programme, avec le mot poly ça fonctionne mais pas avec les autres, car j'utilise les indices ! Mais je vois pas qu'elles sont les autres méthodes !

Voilà merci d'avance !

Édité par Drakop

+0 -0

N'utilise jamais scanf pour récupérer une chaîne de caractère. JAMAIS! Si pas erreur ou volontairement quelqu'un met plus de 256 caractères (dans ton cas), tu as un comportement indéterminé (undefined behaviour), ce qui veut dire que ton programme peut simplement crasher, peut fonctionner normalement, peut supprimer tous tes fichiers, envoyer un mail, faire n'importe quoi, brûler ton ordi… Tu as une fonction qui est parfaite pour ça : fgets

L'idée la plus simple pour résoudre ton problème, est de tester si la sous-chaîne que tu cherches est à chaque position possible dans src. En gros, tu fais une boucle sur chaque caractère de src et dans cette boucle, tu testes si facteur est à cette position de src. Fait attention à ne pas dépasser la fin de src pour tes tests ;)

Il existe aussi d'autres solutions plus efficaces (mais plus compliqués). Typiquement Boyer-Moore est particulièrement efficace et le concept général est assez simple à comprendre.

+0 -0

Salut,

@Berdes a dit tout ce qu’il fallait. Par contre je ne suis pas trop d’accord avec son interdiction sur scanf. Avec %255s, tu te limites à 255 caractères. Et en plus, vu que tu e veux que les mots (donc pas de caractères non alphabétiques), je pense au contraire que scanf est à préférer fgets avec scanf("%255[a-zA-Z]". Et si on veut tout faire bien il faudrait vérifier la valeur retournée et supprimer les caractères restants si besoin.

Je fais un carnage si ce car nage car je nage, moi, Karnaj ! - Tutoriels LaTeX - Contribuez à un tutoriel Ruby

+0 -0

C'est vrai que scanf facilite le boulot pour le coup. Je veux dire ici, on ne se préoccupe ni des accents ni des caractère spéciaux. Du coup scanf est tout indiquée. En condition réelle, effectivement, on aurait certainement utiliser fgets(). Mais dans un "vrai" code, on voudrait aussi gérer les accents. Donc on utiliserait des wchar_t.

Bref, le plus simple comme il a été dis est de recoder strcmp. Qui est simplement une boucle. Et de l'appeler sur chaque chaîne. J'aime particulièrement Boyer-Moore. Si tu as vraiment envie de te compliquer la vie, il y a l'algorithme d'Aho-Corasick que j'ai essayé d'étudier sans succès ^^"

Avec l'algorithme basique, pour chaque lettre, on va voir si on trouve l'un des mots.

Avec Boyer-Moore, on pour chaque mot facteur on va voir si on le trouve dans le mot src et combien de fois on le trouve.


Au niveau de ton code, tu as des problèmes de type. Dans tes scanf, tu n'as pas besoin de mettre l'esperluette ici.

1
scanf("%s", src);

i est unsigned int, mais longueur et longueurFacteur sont des int. Du coup, il a conflit pas très important dans notre cas au niveau des types.

Édité par ache

+1 -0
Auteur du sujet

D'accord merci pour vos réponses, je ne suis pas chez, je ne peux donc pas tester, je vais le faire ce soir, cependant pour la méthode simple:

On doit faire une boucle qui fait toute la chaîne src, caractère par caractère pour vérifier si la chaîne est présente ?

Donc genre ça donnerait quelque chose comme ça ?

1
2
3
4
for(i=0 ; i<longueur ; i++){
   if("facteur"==src[i]
      printf("La chaine est présente.");
}

Mais comment faire pour que "facteur" soit la chaîne qui a été entrée par l'utilisateur avec le scanf ?


D'ailleurs pour le scanf des personnes sont pour d'autres contre

+0 -0
Auteur du sujet

Je vois pas ce que tu veux dire, je dois utiliser deux boucles du coup qui font les deux chaînes ?

Je dois comparer caractère par caractère ? car j'ai déjà essayé, ça ne marche pas avec ce que j'ai fait !

Édité par Drakop

+0 -0
Auteur du sujet
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>

int main(void)
{
    char src[256] = {};
    char facteur[256] = {};
    int compteur = 0;
    unsigned i;

    printf("Saisir le premier mot: ");
    scanf("%s", &src);
    printf("Saisir le deuxiéme mot: ");
    scanf("%s", &facteur);
    int longueur = strlen(src);
    int longueurFacteur = strlen(facteur);
    /* boucle for juqu'à la fin du mot src.
    Le but étant de vérifier que le mot facteur est un facteur de src.*/
    for(i=0 ; i<longueur ; i++){
        //Si la lettre du mot facteur est égale à la lettre du mot src, on incrémente i  
        if(facteur[i] == src[j]){
            compteur++;
        /*l faut ensuite vérifier si la valeur de la variable compteur est égale à la longueur du mot facteur.*/        
        if(compteur == longueurFacteur)
            printf("Le mot %s est bien un mot facteur de %s \n", facteur, src); 
        }

    }

    return 0;
}
+0 -0

Tu dois imbriquer deux boucles. En fait, voici ce que tu dois faire.

1
2
3
4
5
6
7
l = longueur du mot, lF = longueur du facteur
Pour i allant de 0 à (l - lF - 1)
    Si les lettres de mot[i] jusqu’à mot[i + lF] sont celles de facteur Alors
        Afficher "Le mot {facteur} est bien un facteur du mot {mot}."
        Sortir de la boucle
    Fin Si
Fin Pour

Et pour vérifier si les lettres de mot[i] jusqu’à mot[i + lF] correspondent, tu dois faire une deuxième boucle dans laquelle tu compares les lettres une par une.

Je fais un carnage si ce car nage car je nage, moi, Karnaj ! - Tutoriels LaTeX - Contribuez à un tutoriel Ruby

+0 -0
Auteur du sujet

jcomprends plus rien avec ton code :/

-Pour la première boucle pourquoi aller jusqu'à l-lf-1 ?

-Mais du coup après la première boucle dans ton code, la condition vérifie que les lettres de mot[i] jusqu'à mot[i+lf] ensuite à la fin tu me dis pour "pour vérifier si les lettres de mot[i] jusqu’à mot[i + lF] correspondent, tu dois faire une deuxième boucle dans laquelle tu compares les lettres une par une." -> du coup je rajoute une boucle comme ça ? :

1
2
3
4
for(j=0 ; j<(l+lf) ; j++)
{
...
}

Édité par Drakop

+0 -0

Pour la première boucle pourquoi aller jusqu'à l-lf-1

Supposons que je cherche si « mise » est dans « compromis », ce n’est pas la peine de vérifier après avoir vérifié pour le second « o » car il ne reste plus assez de lettre.

En fait, pour cet exemple, on fait ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
l = 9
lF = 4

i = 0
    c != m, ce n’est pas la peine de continuer

i = 1
    o != m, ce n’est pas la peine de continuer

i = 2
    m = m, on continue
    p != i, ce n’est pas la peine de continuer

i = 3
    p != m, ce n’est pas la peine de continuer

i = 4
    r != m, ce n’est pas la peine de continuer

i = 5
    o != m, ce n’est pas la peine de continuer

i = 6, on peut s’arrêter, il ne reste plus assez de lettre dans le mot pour trouver le facteur.

C’est ça que ton algorithme doit faire.

1
2
3
4
5
6
7
for(i = 0 ; i < longueur - longueurFacteur; i++)
{
    /*
      Ici, on regarde si les lettres de facteur sont celles qui se trouvent
      à partir de la i-ème lettre de mot.
    */
}

Je fais un carnage si ce car nage car je nage, moi, Karnaj ! - Tutoriels LaTeX - Contribuez à un tutoriel Ruby

+0 -0
Auteur du sujet
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <string.h>

int main(void)
{
    char src[256] = {};
    char facteur[256] = {};
    int compteur = 0;
    int i=0;
    int j=0;

    printf("Saisir le premier mot: ");
    scanf("%s", &src);
    printf("Saisir le deuxiéme mot: ");
    scanf("%s", &facteur);
    int longueur = strlen(src);
    int longueurFacteur = strlen(facteur);



    for(i=0 ; i<longueur; i++){
            if(facteur[j] == src[i]){
                compteur++;
                printf("%d \n", compteur);
                j++;
                printf("%d %d \n",j, i );
            }
            else
                j=0;


            if(compteur == longueurFacteur){
                printf("Le mot %s est bien un mot facteur de %s \n", facteur, src); 
                return 1;
            }       
    }

    return 0;
}

si vous avez des conseils d'ailleurs n'hésitez pas !

+0 -0
Auteur du sujet

De ce que je vois c'est la méthode algorithme qui n'est pas bonne avec l'indice j mais la je vois pas du tout comment faire malheuresement :/

EDIT : c'est bon j'ai trouvé, j'ai viré le else.

Édité par Drakop

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte