morissardj's Home Page

Home
Langage C

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

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

Main.c

#include <stdio.h>
#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 LSP1(char* mot,int lmot,char* text,int ltext){
      printf("\nLSP1\n");
int i,j;
int *bon_prefix=periode_prefixe(mot,strlen(mot));
//Affiche_tab_int(bon_prefix,strlen(mot));

for(j=0;j<(ltext-lmot+1);j++){
   while((i>=0)&&!(mot[i]==text[j])){
   i=bon_prefix[i];
   }
   i++;
   if(i==lmot){
   printf("%d\n",j);
   i=bon_prefix[lmot];
   }
 }
}

/*******************************************************/
int main(int argc, char *argv[])
{
  char *mot=argv[1];
  char *texte=argv[2];
  printf("\nla chaine est : %s\n",mot);
  int* bon_prefix;
  bon_prefix=periode_prefixe(mot,strlen(mot));
  LSP1(mot,strlen(mot),texte,strlen(texte));
  return 0;
}