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