trouver une chaîne de caractères dans une chaîne de caractères

Version imprimable

Bonjour à tous, je suis étudiant en informatique (je vais entamer ma troisième année) et je suis en pleines révisions avant la rentrée. Je suis en train de bloquer sur un exercice, cela consiste à écrire une fonction indiquant si un mot est facteur d'un autre (exemple : "poly", "copi", et "polycop" sont des facteurs de "polycopié"). J'ai donc répondu à l'exercice en plusieurs fonctions, je vous montre les codes que j'ai fait ainsi que la structure d'un "mot " demandé dans l'exercice.
Code:

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 40 41 42 43 44 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <assert.h> #define NMAX 300 typedef struct { char m[NMAX]; } mot; int est_facteur_gauche(mot facteur_g, mot src){ for(int i=0;facteur_g.m[i]!='\0';i++){ if(facteur_g.m[i]!=src.m[i]){ return 0; } } return 1; } mot copyFromTo(int pos,int end, char tab[]){ assert(pos<=strlen(tab) && end<=strlen(tab) && pos<=end); mot mnew; int nb=0; for(int k=pos;k<=end;k++){ nb++; } mnew.m[nb]; for(int i=pos;i<=end;i++){ mnew.m[i]=tab[i]; } return mnew; } int est_facteur(mot facteur, mot src){ for(int i=0;src.m[i]!='\0';i++){ mot m=copyFromTo(i,strlen(src.m),src.m); printf("i = %d , s= %s\n",i,m.m); if(est_facteur_gauche(facteur,m)){ return 1; } } return 0; }
Je vais donc vous expliquer comment j'ai résonné. La fonction est_facteur_gauche était pour la question précédente demandant de renvoyer un booléen (1 ou 0) selon que le mot facteur_g soit facteur de src ou non. J'ai par la suite décidé d'écrire une fonction renvoyant un mot qui copiait les caractères du mot donné en argument de la position pos à la position end, je me suis dis que ce serait un moyen de vérifier si chaque mot donné à partir de chaque position du mot de départ (src) avait pour facteur le mot "facteur" , si c'était le cas pour aucun des mots, la fonction est_facteur renvoyait 0 (faux) . J'ai donc testé les résultats dans un main que je vous montre ci-dessus :
Code:

1 2 3 4 5 6 7 int main(){ mot m1={"polycopié"}; mot m2={"copi"}; printf("%d",est_facteur(m2,m1)); return 0; }
Cette fonction n'a pas marché, après débogage j'ai remarqué que à l'itération 0, le mot m dont je me suis servi apparaissait, mais aux autres itérations, le mot m était vide. Je précise que dans cet exercice je n'ai pas le droit d'utiliser les fonctions strcpy , strcmp, strngcmp, seulement la fonction strlen(), c'est assez problématique car en C on a pas le droit de modifier des chaines de caractère.. . Pouvez vous s'il vous plait m'éclairer sur mon erreur ?
En vous remerciant d'avances
Bonne journée à vous !

03/09/2020, 22h26
Xelland
c'est qu'il y a un problème dans la méthode copyFromTo

1. elle fait quoi cette ligne ?

Code:

mnew.m[nb];

2. ton pb vient de cette partie :
Code:

1 2 3 for(int i=pos;i<=end;i++){ mnew.m[i]=tab[i]; }
tu crées une nouvelle chaine (mnew) mais l'alimentation est mauvaise

3. pas regardé s'il y avait d'autres pb
03/09/2020, 22h54
foetus
Tu n'as pas besoin de faire 1 copie :mrgreen:

Il faut faire 1 double boucle.
1 boucle for01 pour parcourir la première chaîne str01 moins la taille de la deuxième chaîne str02.
Et à chaque lettre, tu testes avec la lettre la plus à gauche de la deuxième chaîne str02 : str01[i] == str02[0].
Et si les 2 caractères sont égaux :
2.1) Tu mémorises la position de la première chaîne pos
2.2) Tu démarres 1 nouvelle boucle "tant que" les caractères sont égaux str01[pos + j] == str02[j].
2.3) Si tu arrives à la fin de la deuxième chaîne str02, tu arrêtes ton algo - tu as trouvé la sous-chaîne. Sinon tu reprends ta boucle for01 à la position pos
Code:

1 2 3 4 int nb=0; for(int k=pos;k<=end;k++){ nb++; }
:ptdr: :ptdr: :ptdr: :ptdr:

Et tu en penses quoi de nb = (end - pos); (<- à 1 près)

Bonjour

Citation:

Envoyé par MugenTsukyomi

Je vais donc vous expliquer comment j'ai résonné. La fonction est_facteur_gauche était pour la question précédente demandant de renvoyer un booléen (1 ou 0) selon que le mot facteur_g soit facteur de src ou non. J'ai par la suite décidé d'écrire une fonction renvoyant un mot qui copiait les caractères du mot donné en argument de la position pos à la position end, je me suis dis que ce serait un moyen de vérifier si chaque mot donné à partir de chaque position du mot de départ (src) avait pour facteur le mot "facteur" , si c'était le cas pour aucun des mots, la fonction est_facteur renvoyait 0 (faux) .

Inutile de faire tout ça. Ta fonction "facteur_g" suffit. Sauf qu'il faut boucler sur chaque caractère du mot de base (ici "polycopié") et faire le test à partir de la position en cours
Exemple avec "copi"
facteur_g("copi", "polycopié") => 0
facteur_g("copi", "olycopié") => 0
facteur_g("copi", "lycopié") => 0
facteur_g("copi", "ycopié") => 0
facteur_g("copi", "copié") => 1
Accessoirement je ne suis pas certain qu'encapsuler ta chaine dans une structure soit une super idée. A moins que plus tard tu veuilles rajouter des éléments de gestion.

Citation:

Envoyé par MugenTsukyomi

c'est assez problématique car en C on a pas le droit de modifier des chaines de caractère.

Où as-tu rêvé cette assertion ? Tu n'as pas le droit de modifier une chaine statique en mémoire mais tu as parfaitement le droit de modifier une chaine que tu as stockée toi-même.
Exemple
Code:

1 2 3 4 5 char *s="Hello"; # Pointeur vers une zone statique invariable s[0]='X'; # Interdit car justement la zone est invariable char s[]="Hello"; # Tableau qui récupère la chaine depuis la zone statique s[0]='X'; # Ok
Mais de toute façon tu n'as pas besoin de modifier ta chaine, juste de passer le bon pointeur à la fonction "facteur_g()".
Citation:
Envoyé par MugenTsukyomi
Citation:
Envoyé par foetus
Code:

1 2 3 4 int nb=0; for(int k=pos;k<=end;k++){ nb++; }
:ptdr: :ptdr: :ptdr: :ptdr:

Et tu en penses quoi de nb = (end - pos); (<- à 1 près)
C'est vrai que là t'as franchement manqué d'à propos...

Citation:

Envoyé par foetus

Et tu en penses quoi de nb = (end - pos); (<- à 1 près)

T'es sûr de l'utilité des parenthèses ? :D

Citation:
Envoyé par Xelland
c'est qu'il y a un problème dans la méthode copyFromTo

1. elle fait quoi cette ligne ?

Code:

mnew.m[nb];

2. ton pb vient de cette partie :
Code:

1 2 3 for(int i=pos;i<=end;i++){ mnew.m[i]=tab[i]; }
tu crées une nouvelle chaine (mnew) mais l'alimentation est mauvaise

3. pas regardé s'il y avait d'autres pb
Coucou à tous, tout d'abord merci pour vos réponses et désolé si je réponds tardivement, ces derniers temps j'étais un peu pris ^^"
Xelland :
Dans la ligne que tu m'as cité, je voulais créer un tableau de caractères de taille nb (un peu comme on fait en java mais je sais pas si ca se fait pareil)

Foetus :
Merci beaucoup pour ta réponse, grâce à toi , j'ai trouvé la solution ! j'ai donc corrigé mon code, sans me servir des trucs que j'ai écris un peu inutiles ;) J'ai testé la solution en essayant plusieurs cas et ca avait l'air de très bien fonctionner, je pense que ce que j'ai fais est bon. Voilà ce que j'ai corrigé ! :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int est_facteur(mot facteur, mot src){ int pos=0; for(int i=0;src.m[i]!='\0';i++){ if(src.m[i]==facteur.m[0]){ pos=i; int j=0; while(src.m[pos+j]==facteur.m[j]){ if(j==strlen(facteur.m)-1 && src.m[pos+j]==facteur.m[j]){ return 1; } j++; } i=pos+j; } } return 0; }
Merci encore une fois !! J'ai buté sur cette question pendant plusieurs jours à vrai dire !! :lol:

Sve@r :
A vrai dire j'y ai pensé ! J'ai essayé en utilisant la fonction facteur gauche mais ca ne marchait pas ^^" Je ne sais pas pourquoi à vrai dire . Si tu as une solution je suis preneur , sinon ne t'embêtes pas, j'ai résolu mon problème. Merci pour ta réponse également !!

Passez une bonne soirée et merci pour tout !

2-3 remarques sur ton code :

pas la peine d'initialiser des variables à zéro (ou autre valeur) lors de la définition si juste après, tu fais 1 affectation
dans mon explication, tu n'as pas besoin de sauvegarder pos, puisque tu ne réutilises pas le compteur de boucle (et on n'utilise pas 1 pointeur de chaîne)
il faut impérativement repartir de l'endroit où tu as commencé ta boucle while - 2^ième boucle, afin d'éviter les motifs qui se répètent comme copcopcopicop avec copi (<- mais à vérifier pour l'exemple)
pas d'appel aux fonctions dans les tests de boucle (comme strlen)
utilise 1 type non signé comme size_t pour les compteurs
préfixe tes types avec t_ (<- mais ce n'est pas la seule convention de codage qu'il faut avoir)
petite optimisation dont je parlais :whistle: : pas la peine de parcourir ta source en entier, puisqu'à la fin de ta chaîne, tu n'auras plus assez de lettres pour trouver factor (donc de 0 à strlen(src.m) - strlen(factor.m))

Voici 1 code à l'arrache et crado avec des tests et du debug :zoubi:

Code:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
/*****************************************************************************/
/***********************************  Debug **********************************/
/*****************************************************************************/
 
// active debug : gcc -Wall XXX.c
// or : gcc -Wall XXX.c -DD_VERBOSE=1
 
// deactivate debug : gcc -Wall XXX.c -DD_VERBOSE=0
#ifndef D_VERBOSE
    #define D_VERBOSE 1
#endif
 
#if (D_VERBOSE)
    #define DEBUG( XXX ) printf XXX ;
#else
    #define DEBUG( XXX )
#endif
 
 
#define test__ok(TEST_NB, TEST_SRC, SRC_STR, FACTOR_STR) \
{ \
    t_word src    = { SRC_STR }; \
    t_word factor = { FACTOR_STR }; \
\
    if ( is_factor(src, factor) ) { \
        printf("%02lu.%s : SUCCEED\n", TEST_NB, TEST_SRC); \
    } else { \
        printf("%02lu.%s : FAILED\n", TEST_NB, TEST_SRC); \
    } \
}
 
 
#define test_nok(TEST_NB, TEST_SRC, SRC_STR, FACTOR_STR) \
{ \
    t_word src    = { SRC_STR }; \
    t_word factor = { FACTOR_STR }; \
\
    if ( !is_factor(src, factor) ) { \
        printf("%02lu.%s : SUCCEED\n", TEST_NB, TEST_SRC); \
    } else { \
        printf("%02lu.%s : FAILED\n", TEST_NB, TEST_SRC); \
    } \
}
 
 
/*****************************************************************************/
/***********************************  Unit  **********************************/
/*****************************************************************************/
 
#define NMAX 300
 
 
typedef struct {
    char m[NMAX];
} t_word;
 
 
int is_factor(t_word src, t_word factor) {
    size_t fact_len, src_len;
    size_t fact_pos, src_pos;
    unsigned char b_is_not_factor;
 
    fact_len =  strlen(factor.m);
    src_len  = (strlen(src.m) - fact_len);
 
//  assert if (fact_len != 0) && (src_len != 0)
//  assert if (fact_len < src_len)
 
    b_is_not_factor = 1;
 
    for(src_pos=0; (b_is_not_factor && (src_pos <= src_len)); ++src_pos){
        DEBUG( ("is_factor - debug: test 01 between %c and %c\n", src.m[src_pos], factor.m[0]) )
 
        if (src.m[src_pos] == factor.m[0]) {
            if (fact_len > 1) {
                fact_pos = 1;
 
                do {
                    if(src.m[src_pos + fact_pos] == factor.m[fact_pos]) {
                        DEBUG( ("is_factor - debug: test 02 between %c and %c\n", src.m[src_pos + fact_pos], factor.m[fact_pos]) )
 
                        ++fact_pos;
                    }
                } while (b_is_not_factor && (fact_pos < (fact_len - 1)));
 
                if ((fact_pos == (fact_len - 1)) && (src.m[src_pos + fact_pos] == factor.m[fact_pos])) {
                    DEBUG( ("is_factor - debug: test 03 between %c and %c (find)\n", src.m[src_pos + fact_pos], factor.m[fact_pos]) )
 
                    b_is_not_factor = 0;
                } else {
                    DEBUG( ("is_factor - debug: test 03 between %c and %c (%lu <- %lu)\n", src.m[src_pos + fact_pos], factor.m[fact_pos], fact_pos, fact_len) )
                }
            } else {
                DEBUG( ("is_factor - debug: find\n") )
 
                b_is_not_factor = 0;
            }
        }
    }
 
    return (!b_is_not_factor);
}
 
 
/*****************************************************************************/
/***********************************  Main  **********************************/
/*****************************************************************************/
 
int main(int argc, char** argv)
{
    size_t count;
 
    count = 0;
 
    count++; test__ok(count, "test true                   ", "polycopie",     "ycop")
    count++; test__ok(count, "test true  (first)          ", "polycopie",     "pol")
    count++; test__ok(count, "test true  (last)           ", "polycopie",     "copie")
    count++; test__ok(count, "test true, src == factor    ", "polycopie",     "polycopie")
    count++; test_nok(count, "test false                  ", "polycopie",     "copa")
    count++; test__ok(count, "test true,  len == 1        ", "polycopie",     "o")
    count++; test__ok(count, "test true,  len == 1 (first)", "polycopie",     "p")
    count++; test__ok(count, "test true,  len == 1 (last) ", "polycopie",     "e")
    count++; test_nok(count, "test false, len == 1        ", "polycopie",     "z")
    count++; test__ok(count, "test pattern true           ", "copcopcopicop", "copi")
    count++; test_nok(count, "test pattern false          ", "copcopcopicop", "copa")
 
 
    return EXIT_SUCCESS;
}

Citation:

Envoyé par Sve@r

T'es sûr de l'utilité des parenthèses ? :D

:whistle: nous avons plusieurs points de divergence (par exemple, 1 seul retour dans 1 fonction ou pas) et les parenthèses en font partie :mrgreen:
Je surparenthèse tout ... mais je ne suis jamais fait avoir par 1 test ou 1 affectation compliqué, mais des fois pour caler le truc c'est :mur:

Citation:

Envoyé par MugenTsukyomi

A vrai dire j'y ai pensé ! J'ai essayé en utilisant la fonction facteur gauche mais ca ne marchait pas ^^" Je ne sais pas pourquoi à vrai dire

Moi je sais (enfin je n'ai pas de mérite, j'ai découvert le souci en faisant ce TP comme demandé).
Le souci vient de ta fonction "est_facteur_gauche" qui prend en paramètre un mot, un mot entier qu'elle va traiter en entier. Impossible donc de faire en sorte que sur "polycopié" elle ne regade que "ycopié". Elle reçoit une structure contenant le mot, elle traite tout le mot => d'où ma remarque sur cette structure qui n'était pas vraiment nécessaire et ce qui a amené ta solution ~~totalement foireuse~~ un poil excessive où tu recopies dans une mémoire tampon ce que tu veux faire traiter
Solution 1: lui rajouter un paramètre pour lui dire où démarrer dans le mot
Solution 2: changer sa signature et lui faire traiter non pas deux type "mot" mais deux pointeurs sur strings, pointeurs qui eux pourront être positionnés par l'appelant selon ses désirs (je veux traiter "polycopié" je lui passe le pointeur sur "p", je veux traiter "ycopié" je lui passe le pointeur sur "y" et dans les deux cas la fonction part de là pour aller jusqu'à la fin de la string).

C'est la solution 2 que j'ai privilégiée. Mais pour ne pas te déstabiliser, j'ai gardé ensuite cette structure "mot" dans la suite (ok je te dis pas que 2 fois j'ai failli la virer tellement elle me semble inutile)

Citation:

Envoyé par MugenTsukyomi

Si tu as une solution je suis preneur

Pas de souci. Généralement on ne donne pas de solution sauf si l'intervenant montre sa bonne foi ce que tu as fait avec ton exemple.
Code:

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 40 41 42 43 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define NMAX 300 typedef struct { char m[NMAX]; } mot; // Donc la fonction a été modifiée pour ne traiter que des pointeurs mais elle reste identique dans son code à la tienne int est_facteur_gauche(char *facteur_g, char *src){ for (int i=0; facteur_g[i] != '\0'; i++) if (facteur_g[i] != src[i]) return 0; return 1; } int isFactor(mot test, mot src) { size_t i; size_t fin; char *pt; // Pour faire plaisir à foetus qui n'a pas tort quand il dit que si on arrive sur un mot plus petit que le mot à tester on peut s'arrêter) fin=strlen(src.m) - strlen(test.m); // La boucle va faire évoluer un pointeur sur la chaine de base for (i=0, pt=src.m; i <= fin; i++, pt++) if (est_facteur_gauche(test.m, pt)) return 1; // Là je passe à la fonction juste les pointeurs sur la string return 0; } int main(int argc, char *argv[]) { mot src; mot test; strcpy(src.m, argv[1]); size_t i; for (i=2; i < argc; i++) { strcpy(test.m, argv[i]); printf("[%s] - [%s] - %d\n", src.m, test.m, isFactor(test, src)); } }
Voilà. Tu peux tester ce programme en lui passant en premier paramètre le mot de base, puis ensuite tous les mots à tester. Exemple ./prog polycopié xxx yyy poly lyc copié. Le résultat
Code:

1 2 3 4 5 [polycopié] - [xxx] - 0 [polycopié] - [yyy] - 0 [polycopié] - [poly] - 1 [polycopié] - [lyc] - 1 [polycopié] - [copié] - 1

08/09/2020, 00h42
foetus
Citation:

Envoyé par MugenTsukyomi

Xelland :
Dans la ligne que tu m'as cité, je voulais créer un tableau de caractères de taille nb (un peu comme on fait en java mais je sais pas si ca se fait pareil)

Non tu n'as pas compris ce que @Xelland a voulu te dire :mrgreen:
Code:

1 2 3 for(int i=pos0;i<=end;i++){ mnew.m[i]=tab[pos + i]; }
Dans ton code, tu déplaçais le caractère de la position i à la position i au lieu de i - pos.
Et donc en fonction de la création/ taille de ta nouvelle chaîne de caractères soit 1 joli débordement soit les pos premiers caractères non initialisés.