Fiche du TD

Je vous propose pour cet exemple d'utiliser un module. Créons donc un fichier mesfonctions.c dont le contenu est :

// mesfonctions.c

#include <string.h>

int verif_position(char* foin, char* aiguille, int len_aiguille, int shift)
{
    /*
    le premier caractère [0] de aiguille étant
    placé devant le caractère [shift] de foin,
    renvoie 1 si tous les caractères de aiguille concordent à
    leur vis à vis, 0 sinon
    */
    for (int j = 0; j<len_aiguille; j++){
        if (aiguille[j] != foin[shift + j]){
            return 0;
        }
    }
    return 1;
}

int bons_droite(char* foin, char* aiguille, int len_aiguille, int shift)
{
    /*
    le premier caractère [0] de aiguille étant
    placé devant le caractère [shift] de foin.
    compte le nombre de caractères successifs valides
    en partant de la droite de aiguille
    */
    int count = 0;
    for (int j = len_aiguille-1; j>=0; j--){
        if (aiguille[j] != foin[shift + j]){
            return count;
        }
        count += 1;
    }
    return count;
}

void make_rangs(int* arr_rangs, char* aiguille, int len_aiguille)
{
    /* aiguille : chaine de caractères à trouver dans le texte foin
       arr_rangs: tableau contenant les indices des premières occurences
         en partant de la fin.
       exemple : aiguille = "ACCAT"
       arr_rangs = {1, 5, 2, 5,...}
       Les valeurs sont associées aux lettres A, B, C...
       Le premier 1 signifie que le A est à l'indice 1 à partir de la fin
       Le 5 en 2e signifie que B n'est pas présent dans l'aiguille, on
         écrit alors la longueur de aiguille
       Le 2 en 3e signifie que C est à l'indice 2 à partir de la fin
       Remarque : arr_rangs est créé avant l'appel à la fonction.
         la fonction se contente de remplir le tableau
    */
    for (int i=0; i<26; i++){
        arr_rangs[i] = len_aiguille;
    }
    for (int i=len_aiguille-1; i>=0; i--){
        char letter = aiguille[i];
        int indice = letter - 'A';
        if (arr_rangs[indice] == len_aiguille){
            arr_rangs[indice] = len_aiguille - 1 - i;
        }
    }
}

int recherche_naive(char* foin, char* aiguille) {
    /* renvoie l'indice de la première occurence de aiguille dans foin
       si elle existe, -1 sinon.
       utilise une méthode naïve */
    int n = strlen(aiguille);
    int m = strlen(foin);
    for (int s=0; s<=m-n; s++){
        if (verif_position(foin, aiguille, n, s)){
            return s;
        }
    }
    return -1;
}

int recherche_boyer_moore_1(char* foin, char* aiguille){
    /* renvoie l'indice de la première occurence de aiguille dans foin
       si elle existe, -1 sinon.
       utilise une méthode boyer moore avec amélioration 1 du TD */
    int n = strlen(aiguille);
    int m = strlen(foin);
    int rangs[26];
    make_rangs(rangs, aiguille, n);
    int s = 0;
    while (s<=m-n) {
        int b = bons_droite(foin, aiguille, n, s);
        if (b == n) {
            return s;
        } else if (b == 0) {
            char B = foin[s+n-1] - 'A';
            s += rangs[B];
        } else { 
            s += 1;
        }
    }
    return -1;
}

Pour permettre au principal d'atteindre nos fonctions, nous les publions dans un fichier header en *.h :

// mesfonctions.h

int recherche_naive(char* foin, char* aiguille);
int recherche_boyer_moore_1(char* foin, char* aiguille);

Pour le principal, je propose que la commande demande de fournir un nom de fichier et une aiguille. Par exemple :

./main foin.txt ACCATGG

où foin.txt est un fichier texte contenant le foin. Exemple :

foin.txt

ACCGTCTCGTTGTGCACATTCAAGTCACCATGGCATTGCGAGCT

Et voici le principal :

// main.c

#include <stdio.h>
#include "mesfonctions.h"

#define TAILLE_MAX 1000

int main(int argc, char* argv[]) {
    /* Usage de la fonction : ./main nomfichier_foin aiguille */
    if (argc != 3){
        printf("Usage : %s nom_fichier_foin aiguille\n", argv[0]);
        return 1;
    }

    // ouverture du fichier
    FILE* fichier = NULL;
    fichier = fopen(argv[1], "r");
    if (fichier == NULL){
        printf("Échec d'ouverture de %s\n", argv[1]);
    }
    char foin[TAILLE_MAX] = "";
    fgets(foin, TAILLE_MAX, fichier);
    fclose(fichier);
    int i = recherche_boyer_moore_1(foin, argv[2]);
    if (i==-1){
        printf("%s pas trouvé\n", argv[2]);
    } else {
        printf("%s trouvé à l'indie %d\n", argv[2], i);
    }
  return 0;
}