Soluzione dell' HomeWork4aa0203

Vedi anche HomeWork4aa0203, DomandeHomework4aa0203, RisultatiHomework4aa0203.

Questa è la mia implementazione della ricerca di pattern con un numero qualsiasi di asterischi.

L'algoritmo è:

• semplificare il pattern riducendo più asterischi consecutivi ad 1 e rimovendo l'ultimo carattere se è un asterisco.
• per ogni pezzo senza asterischi farne la ricerca a partire dalla posizione successiva a quella trovata dal pezzo precedente
• se il pattern inizia con asterisco il match inizia a carattere zero

Per implementare la ricerca ho modificato la ricerca di una stringa vista a lezione:

• in modo da cercare a partire da un dato punto del pattern e del testo
• in modo da considerare anche l'asterisco come terminatore di stringa

/*
    HomeWork4: ricerca di un pattern in un testo
*/
#include <stdio.h>


/* scommentare la prossima riga per attivare le stampe di debug */
/*
#define DEBUG
*/

/* prototipi */
int  cercaSemplice(char pattern[], int p_start, char testo[], int t_start);
int  semplificaAsterischi(char pattern[]);
void trovaPattern(char pattern[], char testo[], int *posizione);

/************************************************************************
    Algoritmo:
    - semplificaAsterischi
        - riduco ogni sequenza di '*' ad un solo '*'
        - elimino l'ultimo '*' se c'e'
   - se il pattern inizia per '*' la posizione e' 0
   - una alla volta cerco le stringhe del pattern
      - cerco la stringa fino al prossimo '*'
      - salto l' '*'
      - continuo le ricerche dal carattere successivo all'ultima trovata
 ************************************************************************/    
int main(int argc, char * argv[]) {
    /* dichiarazioni                      */
    char * testo;   /* testo                */
    char * pattern;   /* pattern da trovare nel testo         */
    int posizione = 0;   /* posizione del pattern nel testo       */
    int lunghezza = 0;
    int plen;      /* lunghezza del pattern          */

    /* controllo l'input                   */
    if (argc != 3) return 1;
    pattern = argv[1];
    testo   = argv[2];

    /* dati personali                      */
    printf("Andrea\nSterbini\n02\n02\n1961\nsterbini@dsi.uniroma1.it\n");

    /* semplifico il pattern compattando sequenze di asterischi    */
    /* e tolgo l'ultimo carattere se e' un asterisco          */
    plen = semplificaAsterischi(pattern);

    /*    vado avanti nel testo a cercare di far corrispondere il pattern   */
    /*   finche' il testo non e' finito                */

   trovaPattern(pattern, testo, &posizione);
    
    return 0;
}

/************************************************************************
    Trasformo ogni sequenza di asterischi in un solo asterisco
    Tolgo l'ultimo asterisco
    Torno la lunghezza
 ************************************************************************/
int semplificaAsterischi(char pattern[])
{
    int i,j;
    
    if (pattern[0] == '\0')
   return 0;
    /*
   spazzolo il pattern fino alla fine e:
   - finche' trovo un asterisco ed il carattere precedente era asterisco
      copio i caratteri che seguono indietro di un posto
    */
    for (i=1 ; pattern[i] != '\0' ; i---++ )
   while (pattern[i] == '*' && pattern[i-1] == '*' )
       for (j=i ; pattern[j] != '\0' ; j---++ )
      pattern[j] = pattern[j---+1];

    /* torno indietro all'ultimo carattere */
    while (pattern[i] == '\0')
   i--;
    /* rimuovo l'ultimo carattere se e' un asterisco */
    if (pattern[i] == '*')
   pattern[i--] = '\0';
    return i---+1;
}

/************************************************************************
    controllo se il pattern corrisponde alla posizione corrente e torno:
    - lunghezza del testo che corrisponde al pattern
 ************************************************************************/
void trovaPattern(char pattern[], char testo[], int * pos)
{
    /*
   Spezzo il pattern in stringhe separate dagli asterischi
   Cerco la prima stringa, 
   poi la seconda a partire dal carattere seguente
   e cosi' via
    */
    int inizio = 0;   /* inizio del pezzo da cercare del pattern */
    int p  = 0;
    int t_pos  = 0;
   int t_last = 0;
   int i;
   
      /* se il pattern NON inizia con '*' cerchiamo il primo match */   
   if (pattern[0] != '*') {
      /* cerco il primo pezzo del pattern nel testo */
      t_pos = cercaSemplice(pattern,inizio,testo,t_pos);
      /* se non lo trovo faccio fallire la funzione */
      if (t_pos < 0) {
         printf("%d\n%d\n",0,0);
          return;
      }
      /* mi sposto alla posizione trovata */
      t_last = t_pos;
      /* e vado avanti della lunghezza del pezzo trovato */
      while (pattern[inizio] != '*' && pattern[inizio] != '\0') {
         t_last---++;
         inizio---++;
       }
      /* a questo punto t_last e' sul prossimo carattere del match */
   }
    /* salto il prossimo '*' pezzo se c'e' */
    while (pattern[inizio] == '*') {
      /* mi posiziono sul prossimo carattere del testo ? */
      p = t_last;
      /* salto l'asterisco */
      inizio---++;
      /* cerco il pezzo del pattern che parte dalla posizione inizio
      nel testo a partire dalla posizione p */
      p = cercaSemplice(pattern,inizio,testo,p);
      /* se non lo trovo faccio fallire la funzione */
      if (p <= 0) {
         printf("%d\n%d\n",0,0);
          return;
      }
      /* mi sposto alla posizione trovata */
      t_last = p;
      /* e vado avanti della lunghezza del pezzo trovato */
      while (pattern[inizio] != '*' && pattern[inizio] != '\0') {
          t_last---++;
         inizio---++;
       }
      /* a questo punto t_last e' sul prossimo carattere del match */
    }

    /* stampo la posizione e la lunghezza */
   printf("%d\n%d\n",t_pos,t_last-t_pos);
#ifdef DEBUG
   /* se DEBUG e' definita faccio una stampa */
   printf("%s\n%s\n",pattern,testo);
   for (i=0 ; i<t_pos ; i---++)
         printf(" ");
   printf("^");
   if (t_last-t_pos > 1) {
      for (i=0 ; i<t_last-t_pos-2 ; i---++)
         printf(" ");
      printf("^");
   }
   printf("\n");
#endif /* DEBUG */
}

/************************************************************************
    per ogni sequenza di caratteri diversi da '*' del pattern   
   eseguo una ricerca a partire dalla posizione corrente      
 ************************************************************************/



/************************************************************************
    Implementazione della ricerca di una stringa con l'algoritmo naif 
    con la differenza che si considera anche l'asterisco come carattere 
    terminatore
 ************************************************************************/
int cercaSemplice(char pattern[], int p_start, char testo[], int t_start)
{
    int i=t_start,j=0;
    while (testo[i] != '\0') {
      j=0;
      while (   pattern[p_start---+j] == testo[i+j] && 
            pattern[p_start---+j] != '\0' && 
            pattern[p_start---+j] != '*')
          j---++;
      if (pattern[p_start---+j] == '\0' || pattern[p_start+j] == '*')
          return i;
      i---++;
    }
    return -1;
}

-- AndreaSterbini - 13 Nov 2002