Trouver une chaîne dans une autre

Version imprimable

Bonjour !

J'ai un petit soucis avec un exo que j'essaye de faire, je veux trouver dans un mot saisi par l'utilisateur si celui-ci comporte l'autre chaîne saisie par l'utilisateur, sans utiliser les fonctions toutes évidemment ! 8-)

Voilà ce que j'ai essayé de faire :

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
 
 
#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-longueurFacteur+1 ; i++){
        for(j=0 ; i<longueur-longueurFacteur+1; j++)
            if(facteur[i] == src[j]){
                compteur++;
                printf("%d \n", compteur);
 
                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;
}

voilà ce que j'obtient :

Citation:

root@Max:~/Bureau/C# gcc facteur.c

root@Max:~/Bureau/C# ./a.out

Saisir le premier mot: polyco

Saisir le deuxiéme mot: poly

1

0 0

J'ai essayé aussi avec une boucle while

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 <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-longueurFacteur+1 ; i++){
        while(i<longueur-longueurFacteur+1)
            if(facteur[i] == src[j]){
                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;
}

Voilà ce que j'obtient : une boucle infinie

Citation:

Saisir le premier mot: polycop
Saisir le deuxiéme mot: poly
1
1 0
2
1 0
3
1 0
4
1 0
5
1 0
6
1 0
etc

Ce qui est bizarre c'est que mon i ne s'incrémente pas et que il passe dans mon else alors qu'il est passé dans mon if avant ?? :/

Médite :mrgreen: :

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
    const char* substr = /**/;
    unsigned short spos, spos1, dpos;
    unsigned char sc, sc1, dc;
    unsigned char substr_not_found = true;
 
    spos = 0;
    sc = str[spos];
 
    while(substr_not_found && (sc != '\0')) {
        if (((unsigned char) sc) == ((unsigned char) substr[0])) {
            dpos = 1;
 
            spos1 = (spos + 1);
            sc1 = str[spos1];
            dc = (unsigned char) substr[dpos];
 
            while ((sc1 != '\0') && (dc != '\0') && (sc1 == dc)) {
                ++dpos;
                ++spos1;
 
                sc1 = str[spos1];
                dc = (unsigned char) substr[dpos];
            }
 
            substr_not_found = (dc != '\0');
        }
 
        if (substr_not_found) { ++spos; sc = str[spos]; }
    }

24/06/2016, 11h36
drakop

re

Malheureusement ça m'aide pas trop à voir ou j'ai merdé, et j'ai un peu du mal à comprendre le code avec ces noms de variables :/
24/06/2016, 11h47
foetus

Donc tu veux du "clef en main" :fessee: :fessee:

Si tu as une boucle infinie, c'est parce que tu as inversé le if et le while.

Méditation (2): Parce que tu mets en premier le while qui dépend de i alors que ton if fait avancer j.

Citation:

Envoyé par drakop

J'ai un peu du mal à comprendre le code avec ces noms de variables :/

Je ne voulais pas mettre :whistle: destination_char (dc) ou source_char (sc) ou encore source_substr_char (sc1)
24/06/2016, 11h49
drakop

re

Non pas du tout mais c'est juste qu'avec ton code, j'étais pas plus avancé :roll:

Mais merci je vais prendre en compte tes remarques et repasser après !

Et également pourquoi mon programme passe dans le else alors qu'il est passé dans le if juste avant , ça non plus j'ai pas compris :roll:
24/06/2016, 12h35
Matt_Houston

Je te trouve un peu dur foetus. Ceci dit c'est effectivement difficile de te dire ce qui ne va pas drakop sans corriger ton code. Je pense que tu as ici un souci d'algorithmique, pas d'implémentation.

Ton problème correspond à la généralisation du problème suivant : comment déterminer si une chaîne A débute par une autre chaîne B, plus courte ? Vas-y par étapes, réalise déjà un programme qui résoud correctement cela. Tu n'as besoin que d'une seule boucle.

Ensuite, et seulement ensuite, écris un autre programme qui détermine si B est contenue dans A, au début ou ailleurs.

Au départ javais fait ça pour résoudre si une chaine b contient une chaine a plus courte et celui-ci fonctionne uniquement si la chaine est au début du coup :

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
 
 
#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[i]){
            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;
}

et ensuite j'ai fait les codes que j'ai donné au début, pourtant ça me semblait être une bonne méthode :(

J'ai trouvé la solution, pb d'inversion des indices et de la condition dans la boucle :

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
 
 
#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 );
            }
 
 
 
        	if(compteur == longueurFacteur){
            	printf("Le mot %s est bien un mot facteur de %s \n", facteur, src); 
        		return 1;
        	}		
    }
 
    return 0;
}

Après j'imagine que si tu m'as dit que j'avais un problème d'algo, il doit y avoir une meilleure méthode !

25/06/2016, 16h11
foetus
Citation:

Envoyé par Matt_Houston

Je te trouve un peu dur foetus.

Appelle cela comme tu veux, mais ce n'est pas compliqué (*) et mon code est lisible (c'est 2 boucles, 1 test et des incrémentations) ... et assez rapidement.

Et justement, je voulais que quelqu'un en fasse une critique :mrgreen:

* -> Tu vas avoir 2 boucles: 1 pour parcourir ta chaîne en entier et 1 autre pour parcourir ta sous-chaîne pour le test de comparaison.
Et au milieu, un test AAA pour lancer le deuxième parcours.

C'est pour cela qu'il y avait un problème d'algo: si on veut supprimer le test AAA, cela ne doit pas être compliqué, mais ce n'est aussi simple que l'algo que drakop avait proposé.

Citation:

Envoyé par drakop

Après j'imagine que si tu m'as dit que j'avais un problème d'algo, il doit y avoir une meilleure méthode !

Le mien :mrgreen: Je n'ai pas testé mon algo à fond, mais les différences sont:
- Je ne me base pas sur la longueur de la chaîne ni celle de la sous-chaîne. Mais sur la fin de chaîne. Et justement, si j'arrive au bout de la sous-chaîne cela veut dire que je l'ai trouvé. (**)
- Mon algo est XXX (<- je ne connais pas le terme). Par exemple ta chaîne est "popolpolycop" ou "ppopoopolpoly" et ta sous-chaîne est "poly"
** -> Je pense qu'il y a des préconditions à avoir, du genre ta sous-chaîne ne doit pas être vide (1 seul caractère, le '\0').

Salut,

Tu peux aussi faire de la sorte.
Pour chaque lettre du mot à chercher dans l'autre chaine
Pour chaque lettre du mot de l'autre mot à chercher
Si la première lettre du mot à chercher correspond avec une lettre dans l'autre mot
alors tu incrémentes une variable qui indique le nombre de correspondances successives entre les 2 mots et tu passes à la lettre suivante du mot à chercher.
Quand cette variable atteint la taille du mot à chercher alors tu as trouvé ce mot dans l'autre chaîne.
En cas d'échec, tu réinitialises cette variable à 0, tu repars depuis la lettre précédentes dans l'autre mot et tu repars à 0 dans le mot à chercher.

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
 
 /** *****************************************************************************************************************************************************************************************************************************
 * \fn short str_find( const char *str_in, const char *pattern );
 *********************************************************************************************************************************************************************************************************************************
 * \brief Tells if yes or not the specified pattern has been found in the string
 *********************************************************************************************************************************************************************************************************************************
 * \param      str_in[const char*] &rarr; A string
 * \param      pattern[const char*] &rarr; A string
 * \return     status[short] &rarr; A boolean
 *
 * /note str_find return TRUE if it does find the patter in the string
 * /note str_find return FALSE if it does find the patter in the string
 * /note str_find will stop at the first match.
 *
 *********************************************************************************************************************************************************************************************************************************/
short str_find( const char *s, const char *pattern )
{
    if (s && pattern) //T0
    {
        unsigned long long int pattern_lengh=0;
        unsigned long long int i,j;
        for (i=0 ; i<strlen(pattern) ; i++)
        {
            for ( j=0 ; j<strlen(s) ; j++ )
            {
                if( s[j]==pattern[i] )
                {
                    pattern_lengh++;
                    i++;
                    if ( pattern_lengh==strlen(pattern))
                        return 1;
                }
 
                else
                {
                    if (pattern_lengh>=1)
                        j--;
 
                    i=0;
                    pattern_lengh=0;
                }
            }
 
            if(j==strlen(s))
                return 0;
        }
    }
    else
    {
        if (!s)
            printf("\nstr.h::str_find -> s is NULL");
        if (!pattern)
           fprintf("\nstr.h::str_find -> pattern is NULL");
    }
    return 0;
}

Cordialement.