Solution plus optimisée, trouvez le nombre de sous-chaînes dans une chaîne. En utilisant C

Question

Donc, j'ai une tâche pour trouver le nombre de sous-chaînes dans une chaîne donnée. Je ne peux utiliser aucune bibliothèque C pour effectuer cette tâche. stringExist ne peut avoir que 2 chaînes en tant que paramètres.

Ma solution fonctionne, mais j'ai le sentiment qu'il devrait y avoir une manière plus élégante de faire cette tâche. Solution 1:il se trouve, il ne fonctionne pas correctement

#include <stdio.h> 

int stringExist(char string[], char s2[]); 

int main(void){ 
    char string[] = "strstrASDstrSTRst"; 
    char s2[] = "str"; 
    printf("Final result: %i\n",stringExist(string,s2)); 
    return 0; 
} 

int stringExist(char string[], char s2[]){ 
/* I am aware that I can init all this values in one row */ 
    int count = 0; 
    int size = 0; 
    int i = 0; 
    int temp = 0; 
    int result = 0; 

    while(s2[size]!='\0'){   
     size++; 
    } 

    while(string[i]!='\0') 
    {   
     if(string[i]==s2[0]) 
     { 
      printf("Found first occurrence\n"); 
      count=0;    
      while((temp=(string[i]==s2[count]))!=0) 
      {    
       count++;      
       if(size==count){ 
        printf("Match\n"); 
        result++;      
        break;      
       } 
       i++; 
      } 
     } 
     i++; 
    } 


    return result; 
} 

Solution numéro 2:

Jusqu'à présent, aucune erreur trouvée. J'ai fait une traversée de chaîne un peu différente, maintenant je n'incrémente pas i dans la boucle de comparaison de caractères.

#include <stdio.h> 

int stringExist(char string[], char s2[]); 

int main(void){ 
    char string[] = "bobobobojkhhkjjkhbo;klkl;bobo"; 
    char s2[] = "bobo"; 
    printf("Final result: %i\n",stringExist(string,s2)); 
    return 0; 
} 

int stringExist(char string[], char s2[]){ 
    int count = 0; 
    int size = 0; 
    int i = 0; 
    int c = 0; 
    int temp = 0; 
    int result = 0; 

    while(s2[size]!='\0'){  
     size++; 
    } 
    for(i=0;string[i]!='\0';i++){ 
     if(string[i]==s2[0]) 
     { 
      printf("Found first occurence at %i\n",i); 
      count = 0; 
      c = i;    

       while((temp=(string[c]==s2[count]))!=0) 
       {  
        printf("Count %i, I %i, current char: %c\n",count, c,string[c]); 
        count++;      
        if(size==count){ 
         printf("Match\n"); 
         result++;     
         break;     
        } 
        c++; 
       } 

     } 
    } 


    return result; 
} 

Merci pour vos suggestions, Vitaly

Answer 1

Cela se sent comme une question de devoirs - dans ce cas, vous devriez certainement le faire vous-même. Mais, quelque chose que vous voudrez probablement vérifier pour que je ne pense pas que votre code gère correctement maintenant est la suivante:

Combien de fois "bobo" apparaît dans la chaîne "bobobo". Cela devrait probablement être deux fois et je pense que votre code ne comptera qu'un seul.

Bonne chance, Marque.

Answer 2

Eh bien, d'un point de vue algorithmique, ce n'est pas si mal. Vous pouvez faire des optimisations, mais je ne pense pas que ce soit le cas (ça ressemble à des devoirs!).

Vous pouvez avoir un léger problème: dans une chaîne comme "hahahaha", combien de fois "haha" doit-il être détecté? Deux fois? Trois fois? Votre code le verrait deux fois. D'un point de vue stylistique, il y a certainement place à l'amélioration, mais vous apprendrez cela au fil du temps, en codant et en lisant le code des autres =). Persévère!

Answer 3

Je suggère de l'écrire comme vous le feriez si vous étiez autorisé à utiliser les fonctions de la bibliothèque. Puis revenez en arrière et écrivez vos propres versions des fonctions de bibliothèque que vous avez utilisées. Alors que l'écriture de versions hautement optimisées des fonctions string.h peut être difficile, écrire des versions décentes de la plupart d'entre eux en C est assez simple.

L'utilisation de sous-routines (fonctions) pour préformer les sous-tâches de ce problème vous aidera de garder votre code clair et aussi éviter certains types de problèmes, tels que si vous avez appelé:

x = stringExist("aaaaa", "aa"); 

Il y a 4 occurences de la chaîne « aa » dans « AAAAA », mais je ne pense pas que votre fonction va tous les trouver. La raison en est que lorsque vous recherchez dans la chaîne la plus grande pour les occurrences de la seconde, vous utilisez le même index pour le début de la chaîne et dans la chaîne. En fait, il semble que vous obtiendrez les mauvais résultats pour:

x = stringExist("tBatBath", "tBath"); 

À moins bien sûr, je l'ai mal compris ce que la fonction était censé faire.Si vous deviez écrire votre propre version d'une fonction de comparaison de préfixe de chaîne (essentiellement memcmp ou strncmp) alors vous auriez séparé le travail de faire correspondre la longueur de la chaîne de regarder plus en profondeur dans la chaîne et n'aurait probablement pas fait une telle erreur.

Si vous ne vous souciez pas de réduire l'efficacité de vos fonctions et la surcharge des fonctions d'appel, ne vous inquiétez pas. D'abord, ce n'est pas si grave. Deuxièmement, il suffit de les déclarer inline ou static inline et si vous compilez avec l'optimisation activée, le compilateur générera très probablement du code aussi bon qu'il le ferait sans l'utilisation de plusieurs fonctions.

Answer 4

pilait: (fonctionne aussi pour la condition supplémentaire)

int stringExist(char *string, char *sub) 
{ 
    int count = 0; 

    while(*string) 
    { 
    char *a = string, *b = sub; 
    while(*a && *a == *b) {a++;b++;} 
    count += !*b; 
    ++string; 
    } 

    return count; 
}