Recherche Boyer Moore en C

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;
}

À cause du tableau que nous utilisons pour stocker les rangs, nos fonctions ne sont valables que si le foin ne contient que des caractères dans A-Z. Si on ajoute un caractère en dehors, le fonctionnement n'est pas garanti : on pourra avoir une erreur franche ou bien une boucle infinie.

Vous remarquez qu'on choisit de passer l'argument len_aiguille à diverses fonctions. C'est un usage courant en C. Calculez la longueur de la chaîne prend du temps : il faut parcourir le tableau de caractères (une chaîne est un tableau de char en C) jusqu'à trouver le caractère \0 signifiant la fin de chaîne. Donc on évite de le refaire si on l'a déjà fait avant.

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);

Ce fichier ne contient que les signatures de fonctions. Inutile de publier les autres fonctions car celles cis ne sont pas utilisées en dehors de mesfonctions.c.

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;
}