Une chaîne dans une autre ! en C.

Le problème exposé dans ce sujet a été résolu.

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 !

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

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

+1 -0

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

Tu ne peux pas faire une comparaison comme ça.

Tu dois faire une comparaison "à la main" dans une autre boucle.

+1 -0

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

Oui, tu dois comparer caractère par caractère. Montre nous le code que tu as utilisé pour le faire.

+0 -0 
 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.

+0 -0

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++)
{
...
}
+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.
    */
}
+0 -0 
 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

Non, ton code ne fonctionne pas. Essayes par exemple avec le mot « bababar » et le facteur « babar ».

+0 -0

Teste ton algo à la main sur l’exemple que j’ai donné. Tu verras quel est le problème.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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