Aos monitores...

[Andrew Yuan <andrewy@terra.com.br>]

Um dos componentes do meu grupo deu uma modificada indevida no EP, antes
de entregá-lo, no arquivo ep4a.c. 

Os componentes do grupo são:
Andrew Gan King Yuan
Marcio Fumihiko Suenaga
Wagner Tsuchiya

Estou mandando o arquivo ep4a.c retificado e estou deixando disponível o
EP na minha página (www.linux.ime.usp.br/~andrew/downloads), ou, para
que ele funcione, vc deve dar um argumento a mais na linha de comando
para o programa ep4a. 
Obrigado!
Andrew....
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 5000000
#define MAXQ 100
#define key(A) (A)
#define eq(A, B) (strcmp(A,B)==0)
#define less(A, B) (strcmp(A,B)<0)
#define NULLitem (NULL)
#define digit(A, B) A[B]
#define NULLdigit (0)


int m=30;


static char text[MAXN];

typedef char *Item;
typedef char *Key;

typedef struct STnode* link;
struct STnode {
	int d;
  long int p;
	link l, m, r;
};
static link head[256];


void STinit();
link NEW(int d, long int p);
/*Item searchR(link h, Key v, int w);
Item STsearch(Key v);*/
link insertR (link h, Item item, int w, long int p);
void STinsert(Key key, long int p);
void printKey(link h, Key key);
void geraArquivoR (FILE *arquivo, link h);
void geraArquivo (char *nomArquivo, link *h);

int main (int argc, char *argv[])
{
	int t, N=0;
	long int i;
	FILE *entrada;
	char saida[MAXQ];
	Key chave;
	link l;
	if (argc != 2) {
	  printf ("Erro no uso do programa\n");
	  printf ("%s arquivo_de_entrada query\n", argv[0]);
	  return 1;
	}
	strcpy (saida, argv[1]);
	for (i = 0; saida[i]!='.'; i++);
	i++;
	saida[i]='i'; i++;
	saida[i]='d'; i++;
	saida[i]='x';
	entrada = fopen(argv[1], "r");

	while ((t=getc(entrada)) != EOF){
	  if (N < MAXN-1){
	    if (t == '\t' || t == '\n' || t == '\0') t = ' ';
	    text[N++] = t;
	  }
	  else{
	    scanf ("%d", &i);
		 printf ("\nTexto nao coube em sua totalidade no vetor!\n\n");
		 break;
		}
	}
	text[N]='\0';
	// 	 for (i=0; i<N; i++)
	// 	putchar(text[i]);
	chave=text;
	// printf ("%s", chave);
	STinit();
	i=-1;
	do {
	  chave=&text[++i];
	  STinsert (chave, i);
	  //printf ("%s\n\n", chave);
	  while (text[i]!=' ') {
	    i++;
	    if (text[i]=='\0')
	      break;
	  }
	} while (text[i]!='\0');
	  /* while (l!=NULL){
	    printf ("%c", l->d);
	    l=l->m;
	    }*/

	/*for (l=head['s']; l!=NULL; l=l->m)
		printf ("%c %d\n", l->d, l->p);
	printf ("%s!!%d\n", STsearch(query), argc);*/

	geraArquivo(saida, head);

	return 0;
}



void STinit()
{
	int i;
	for (i=0; i<256; i++)
		head[i]=NULL;
}

link NEW(int d, long int p)
{
	link x = malloc (sizeof *x);
	if (x==NULL) {
	    printf ("Erro na alocacao de memoria!");
		return NULL;
	}
	x->d = d;
	x->p = p;
	x->l = NULL;
	x->m = NULL;
	x->r=NULL;
	return x;
}
/*
Item searchR(link h, Key v, int w)
{
	int i = digit (v, w);
	if (h== NULL) return NULLitem;
	if (h->p != -1){
		for (w=0; digit(text, h->p + w) != NULLdigit; w++){
			if (digit(v, w) == NULLdigit){
				printKey(h, v);
				return v;
			}
			if (digit(v, w) != digit(text, h->p +w) && digit(v, w)!= '*')
				break;
		}
		return NULLitem;
	}

	//printf ("%s", &text[h->p]);
	if (i == NULLdigit){
		printKey(h, v);
    	return v; // procurar dentro deste if todas as folhas de todas as subárvores
	}
	if (i < h->d && i!='*') return searchR(h->l, v, w);
	if (i == h->d || i == '*') return searchR(h->m, v, w+1);
	if (i > h->d && i!='*') return searchR(h->r, v, w);
	return NULLitem;
}

Item STsearch(Key v)
{
	return searchR(head[v[0]], v, 1);
}
*/
link insertR (link h, Item item, int w, long int p)
{
	Key v = key(item);
	int i = digit(v, w);
	if (h== NULL) {
		h=NEW(i, p);
		return h;
	}
	if (i == NULLdigit) return h;
	if (h->p!=-1){
		h->m = NEW(digit(text, w+1+h->p), h->p);
		h->p = -1;
	}
	if (i < h->d) h->l = insertR(h->l, v, w, p);
	if (i == h->d) h->m = insertR(h->m, v, w+1, p);
	if (i > h->d) h->r = insertR(h->r, v, w, p);
	return h;
}

void STinsert(Key key, long int p)
{
	head[key[0]] = insertR(head[key[0]], key, 1, p);
}

void printKey(link h, Key key)
{
	int i, j;
	if (h->p != -1){
		printf ("%ld:\t", h->p);
		j=m;
		while (h->p -j < 0) j--;
		for (; j > 0; j--)
			putchar (text[h->p - j]);
		for (i=h->p; digit(key, i-h->p) != NULLdigit; i++)
			putchar (text[i]);
		for (j=0; j<m && text[i]!='\0'; j++, i++)
			putchar (text[i]);
		printf ("\n");
		return;
	}
	//if (h->m != NULL)
		printKey(h->m, key);
	if (h->l != NULL)
		printKey(h->l, key);
	if (h->r != NULL)
		printKey(h->r, key);
}

void geraArquivoR (FILE *arquivo, link h) {
  fprintf (arquivo, "%ld ", h->p);
  fprintf (arquivo, "%d ", h->d);
  if (h->l != NULL)
    geraArquivoR (arquivo, h->l);
else
  fprintf (arquivo, "-2 ");
  if (h->m != NULL)
    geraArquivoR (arquivo, h->m);
else
  fprintf (arquivo, "-2 ");
  if (h->r != NULL)
    geraArquivoR (arquivo, h->r);
else
  fprintf (arquivo, "-2 ");
  return;
}

void geraArquivo (char *nomArquivo, link *h) {
  FILE *arquivo;
  int i;
  arquivo = fopen (nomArquivo, "w");
  for (i = 0; i < 256; i++){
    if (h[i] != NULL){
      fprintf (arquivo, "%d ", i);
      geraArquivoR (arquivo, h[i]);
      fprintf (arquivo, "-3 ");
    }
  }
  fprintf (arquivo, "-4\n");
  fclose (arquivo);
  return;
}