morissardj's Home Page

Home
Langage C

Langage C - Recherche de mots dans un texte LSP (Pratt-Morris-Knuth)

Définition de l'algorithme naïf
Soit un texte W définit sur un alphabet A, nous voulons chercher un mot M définit sur un alphabet B (B inclus dans A), l'idée est de se servir des informations que l'on a sur le mot que l'on recherche, en l'occurrence on va se servir des la périodicité du mots.
La périodicité du mot, est l'étude de tout ses suffixes et voir si dans ces sous mots il existe des suffixes égaux aux préfixes...

Algorithme
...........................

Source

exemple pour tester et voir la difference.
>main.exe aataataa taataataacaataa MP
>main.exe aataataa taataataacaataa MPK

Main.c

/*Recherche LSP
Implementation de jerome morissard
Algorithme de Morris-pratt-Knuth souvent abrégé par algorithme KMP
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Fonction qui calcul la periode de chaque prefixe*/
int* periode_prefixe(char* mot,int longueur){
int i=0;
int j;
int *period=(int*)malloc(sizeof(int)*longueur) ;
period[i]=-1;
for(j=1;j<=(longueur-1);j++){
   period[j]=i;
   while(  (i>=0) && !(mot[i]==mot[j])  ){
   i=period[i];
   }
   i++;
}
period[longueur]=i;
return period;
}
/*******************************************************/
void Affiche_tab_int(int* tab, int longueur){
     int i;
     for(i=0;i<longueur;i++){
        printf("%d",tab[i]);
     }
     printf("\n");

}

/*******************************************************/
void Affiche_tab_char(char* tab,int longueur){
     int i;
     for(i=0;i<longueur;i++){
        printf("%c",tab[i]);
     }
     printf("\n");
}
/*******************************************************/

void LSP_MPK(char* mot,int lmot,char* text,int ltext){
printf("\nLSP\n");
int i,j;
int *bon_prefix=periode_prefixe(mot,strlen(mot));
int nombredecomparaison=0;
int nombrededecalage=0;
for(j=0,i=0;j<ltext;j++){
   while((i>=0)&&!(mot[i]==text[j])){
   /*ici se situe l'amelioration de Knuth*/

/*1. si la lettre qui a cause le miss match est la meme que celle ...*/
        if((mot[i]==mot[bon_prefix[i]])){
         i=-1;
         nombrededecalage++;
        }
   /*2. sinon se deplacer de bon pref*/
        else{
          i=bon_prefix[i];
          nombrededecalage++;
        }
   }
   i++;
   nombredecomparaison++;
   if(i==lmot){
     printf("%d\n",j-lmot+1);
     i=bon_prefix[lmot];
     nombrededecalage++;
   }
 }
printf("Nombre de comparaison %d\n",nombredecomparaison);
printf("Nombre de decalage %d\n",nombrededecalage);
}

/*******************************************************/
void LSP_MP(char* mot,int lmot,char* text,int ltext){
printf("\nLSP\n");
int i,j;
int *bon_prefix=periode_prefixe(mot,strlen(mot));
int nombredecomparaison=0;
int nombrededecalage=0;
for(j=0,i=0;j<ltext;j++){
   while((i>=0)&&!(mot[i]==text[j])){
     i=bon_prefix[i];
     nombrededecalage++;
   }
   i++;
   nombredecomparaison++;
   if(i==lmot){
     printf("%d\n",j-lmot+1);
     i=bon_prefix[lmot];
     nombrededecalage++;
   }
 }
printf("Nombre de comparaison %d\n",nombredecomparaison);
printf("Nombre de decalage %d\n",nombrededecalage);
}

/*******************************************************/
int main(int argc, char *argv[])
{
  char *mot=argv[1];
  char *texte=argv[2];
  char *mode=argv[3];
  char *mode_default="MPK";

int resultat=strcmp(mode_default,mode);
  printf("\nle mot est : %s\n",mot);
  int* bon_prefix;
  bon_prefix=periode_prefixe(mot,strlen(mot));
  //printf("Affiche bon pref\n");
  //Affiche_tab_int(bon_prefix,strlen(mot)+1);
  if(resultat==0){
    LSP_MPK(mot,strlen(mot),texte,strlen(texte));
  }
  else{
    LSP_MP(mot,strlen(mot),texte,strlen(texte));
  }
  return 0;
}