Programme de l'algorithme naif en C

Salut yira,

Si l'algorithme n'est pas donné, tu dois le déterminer avant de te lancer dans le codage en C.

Cette page peut certainement t'aider :https://www.irif.fr/~carton//Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/

Cependant, il te faudra voir ton cours pour valider si cet algorithme comporte une "boucle interne", et ne comporte pas de "boucle rapide" ou de "sentinelle". Ce sont des notions qui ont dû t'être expliquées par la personne ayant rédigé l'énoncé (ton enseignant?).

En ce qui concerne ton code C. Tu devrais sérieusement revoir tes bases.

Je pense que tu confonds la syntaxe de déclaration d'une fonction et celle de déclaration d'un tableau avec tes x et y et le prototype de ta fonction n'a pas de sens pour moi.

Voilà une charpente de code C comportant un prototype raisonnable pour cette fonction, et permettant de tester l'implémentation de ton algorithme.

Je me permets de citer le passage du cours de M. Olivier CARTON, situé à l'adresse précitée, en commentaire de la fonction

int premiere_occurrence(char * motif, char * texte)

.

#include <stdio.h>

/**
 * premiere_occurrence - recherche naïve de texte
 *
 * motif : motif à rechercher
 * texte : texte où le motif est recherché
 *
 * retourne :
 *  -1 si le motif n'est pas présent
 *  ou la position de la première occurence
 */
int premiere_occurrence(char * motif, char * texte)
{
    /*
     * Pour chaque position possible du motif dans le texte,
     * on teste si cette position est une occurrence du motif.
     * Ce test est effectué en comparant les caractères du
     * motif avec les caractères du texte de gauche à droite.
     * Si tous les caractères du motif sont égaux aux
     * caractères du texte aux positions correspondantes,
     * une occurrence a été trouvée et la position de cette
     * occurrence est retournée. Sinon, la recherche se poursuit
     * en passant à la position suivante.
     */
}

int main(void)
{
    char * motif = "Toto";
    char * texte = "Le professeur demande à Toto :\n"
            "- Toto, 3 et 3 ça fait quoi ?\n"
            "- Match nul monsieur !";
    int position;

    position = premiere_occurrence(motif, texte);

    if (position == -1)
    {
        printf("motif [%s] non trouvé dans le texte\n", motif);
    }
    else
    {
        printf("le motif [%s] a été trouvé en position %d\n", 
                motif, position);
        /* le résultat correct est 25 */
    }

    return 0;
}

A toi de jouer :-)


Dal

Si tu veux compter le nombre d'occurrences, en principe, il "suffit" de modifier l'algorithme pour qu'au lieu de retourner la position de la première occurrence, il incrémente un compteur d'occurrences et continue la recherche sur la suite de la chaine de texte, puis retourne le compteur lorsque la fin de la la chaine de texte est atteinte.

Cela dit, je ne m'y connais pas trop en molécules d'ADN.

Si tu as "CGCAACAT", et que tu cherches "ACAT", tu vas le trouver, et si tu recherches "CGCAA" tu vas le trouver aussi, et je ne sais pas si le fait qu'ils partagent un caractère a une importance pour toi, en particulier si ta recherche doit indiquer le nombre d'occurrences de "ACAT" et de "CGCAA".


Dal