#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>


#define TRUE 1
#define FALSE 0

#define TRACEON FALSE

#define MAX_ETATS 50
#define MAX_ALPHA 128
#define MAX_TRANS 5

#define MAX_L_MOT (MAX_ETATS-2)
#define DIM_LISTE (MAX_L_MOT*MAX_L_MOT)

                        /* MAX_ETATS  nombre maximum d'etats qu'un automate peut avoir
                        /* MAX_ALPHA  differentes etiquettes existantes pour les transitions (set ASCII)
                        /* MAX_TRANS  nombre maximum de transitions avec la meme etiquette depuis un meme etat
			/* MAX_L_MOT  longueur maximale d'un mot a' traiter 
			/* DIM_LISTE  dimension de la liste des sousmots d'une longueur donne' 




 
/******************************************************************************

           Projet d'Algorithmique: Outil de Recherche de Sousmots
    Licence Informatique 1999-2000,  Universite de Marne la Vallee (FRANCE)
         Copyright (C) 2000 Daniele Raffo  <draffo@ken.univ-mlv.fr>
                               mars-avril 2000


    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *******************************************************************************/







/* modele utilise' pour l'automate */
typedef struct {
        int table[2*MAX_ETATS][MAX_ALPHA][MAX_TRANS];           /* table des transitions */
        int status[2*MAX_ETATS];
						/*  status = 0 : etat                      */
                                                /*           1 : etat initial              */
                                                /*           2 : etat terminal             */
                                                /*           3 : etat initial et terminal  */
                                                /*          -1 : nonexistent               */     
} automate;
                

/* modele utilise' pour garder la liste des sousmots d'une longueur donnee */ 
typedef struct {
        char sousmot[MAX_L_MOT];   /* sousmot                                                          */
        int terminus;              /* l'etat ou' on arrive quand on lit la derniere lettre du sousmot  */
        int unique;                /* flag: si TRUE ce sousmot distingue le deux mots                  */
} liste_sousmots;


int equivhalt;                     /* flag: si TRUE non-equivalence des deux automates */

int dummy;                         /* variables dummy */
automate adummy;










main(int argc, char *argv[]) 
{

        void main_interactif(char *nomprog);
	void main_ligne_de_commande(int argc, char *argv[]);


	if (argc==1) main_interactif(argv[0]);
	else main_ligne_de_commande(argc, argv);

}




void main_interactif(char *nomprog)
{

        void init_automate(automate *a);
	int lit_fichier(char *afile, automate *a);
	void ecrit_automate(FILE *fp, const automate *a);
	void error(int erreur, int datanum, char *datastr);
	int equiv_automate(char *afile1, char *afile2);
	automate automate_sousmots(const char mot[]);
	void tous_les_sousmots(FILE *fp, const char *mot_a_traiter);
	void distingue(FILE *fp, const char *mot1, const char *mot2);
	int output_sur_ecran(void);

        automate autom1, autom2;
        char fichier1[80]; char fichier2[80];
	char mot1[MAX_L_MOT]; char mot2[MAX_L_MOT];
	FILE *outputp;
	char outputfile[80];
        char choix;
        int reponse;


	while (TRUE) {

 	        fprintf(stdout, "\n\n\n\n     ----------------------------------------------------------------------");    
		fprintf(stdout, "\n             Projet d'Algorithmique: Outil de Recherche de Sousmots");    
		fprintf(stdout, "\n\n                              Licence Informatique");    
		fprintf(stdout, "\n                     Universite de Marne la Vallee (FRANCE)");    
		fprintf(stdout, "\n\n           Copyright (C) 2000 Daniele Raffo  <draffo@ken.univ-mlv.fr>");    		
		fprintf(stdout, "\n\n       Ce programme est libre et vous etes encourage' a' le redistribuer");
		fprintf(stdout, "\n             sous les conditions du Licence Publique Generale GNU.");
 	        fprintf(stdout, "\n     ----------------------------------------------------------------------");    
		fprintf(stdout, "\n\n\n   %s -help pour les instructions sur l'usage en ligne de commande", nomprog);
		fprintf(stdout, "\n\n  1)  Examiner un automate");    
		fprintf(stdout, "\n  2)  Tester l'equivalence de deux AFD complets");    
		fprintf(stdout, "\n  3)  Creer l'AFD complet des sousmots d'un mot");    
		fprintf(stdout, "\n  4)  Lister les sousmots d'un mot");    
		fprintf(stdout, "\n  5)  Calculer les sousmots qui distinguent deux mots");    
		fprintf(stdout, "\n\n  X)  Sortie");    
		fprintf(stdout, "\n\n\nOperation: "); 
		fflush(stdin); scanf("%c", &choix);        
		/* c'est mieux de nettoyer toujours le stdin avant d'y lire avec le scanf */    
		fprintf(stdout, "\n");


		switch(toupper(choix)) {

		        case '1':
			        fprintf(stdout, "Nom du fichier: "); 
				fflush(stdin); scanf("%[^\n]", fichier1); 

				init_automate(&autom1);
				dummy=lit_fichier(fichier1, &autom1);  
				ecrit_automate(stdout, &autom1);
			        break;

		        case '2':
			        fprintf(stdout, "Nom du premier fichier: "); 
				fflush(stdin); scanf("%[^\n]", fichier1); 
			        fprintf(stdout, "Nom du deuxieme fichier: "); 
				fflush(stdin); scanf("%[^\n]", fichier2);

				reponse=equiv_automate(fichier1, fichier2);
				fprintf(stdout, "\n\nLes deux automates ");
				if (reponse) fprintf(stdout, "ne reconnaissent pas le meme langage");
				else fprintf(stdout, "reconnaissent le meme langage");
			        break;

		        case '3':
			        fprintf(stdout, "Mot: "); 
				fflush(stdin); scanf("%[^\n]", mot1);

				init_automate(&autom1);
				autom1=automate_sousmots(mot1);
				if (output_sur_ecran()) ecrit_automate(stdout, &autom1);
				else {
				        fprintf(stdout, "Fichier de output: "); 
					fflush(stdin); scanf("%[^\n]", &outputfile);
					if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile);
					else ecrit_automate(outputp, &autom1);
					fclose(outputp);	/* pas de probleme pour stdout, il ne sera pas ferme' */		
				}
			        break;

		        case '4':
			        fprintf(stdout, "Mot: "); 
				fflush(stdin); scanf("%[^\n]", mot1);

				init_automate(&autom1);
				autom1=automate_sousmots(mot1);
				if (output_sur_ecran()) tous_les_sousmots(stdout, mot1);
				else {
				        fprintf(stdout, "Fichier de output: "); 
					fflush(stdin); scanf("%[^\n]", &outputfile);
					if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile);
					else tous_les_sousmots(outputp, mot1);
					fclose(outputp);
				}
			        break;

		        case '5':
			        fprintf(stdout, "Premier mot: "); 
				fflush(stdin); scanf("%[^\n]", mot1); 
			        fprintf(stdout, "Deuxieme mot: "); 
				fflush(stdin); scanf("%[^\n]", mot2);

				if (output_sur_ecran()) distingue(stdout, mot1, mot2);
				else {
				        fprintf(stdout, "Fichier de output: "); 
					fflush(stdin); scanf("%[^\n]", &outputfile);
					if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile);
					else distingue(outputp, mot1, mot2);
					fclose(outputp);
				}
				break;

		        case 'X':
			        exit(0);

		}

        }
	  
}




void main_ligne_de_commande(int argc, char *argv[])
{

        void init_automate(automate *a);
	int lit_fichier(char *afile, automate *a);
	void ecrit_automate(FILE *fp, const automate *a);
	void error(int erreur, int datanum, char *datastr);
	int equiv_automate(char *afile1, char *afile2);
	void tous_les_sousmots(FILE *fp, const char *mot_a_traiter);
	void distingue(FILE *fp, const char *mot1, const char *mot2);

	automate autom;
	FILE *reference;


	if ((!strcmp(argv[1],"-e"))&&(argc==4)) exit(equiv_automate(argv[2], argv[3]));


	else if ((!strcmp(argv[1],"-m"))&&(argc==4)) distingue(stdout, argv[2], argv[3]);

	else if ((!strcmp(argv[1],"-m"))&&(argc==5)) {
	        if ((reference=fopen(argv[4], "w"))==0) error(5, 0, argv[4]);
		else distingue(reference, argv[2], argv[3]);
	}


	else if ((!strcmp(argv[1],"-s"))&&(argc==3)) tous_les_sousmots(stdout, argv[2]);

	else if ((!strcmp(argv[1],"-s"))&&(argc==4)) {
	        if ((reference=fopen(argv[3], "w"))==0) error(5, 0, argv[3]);
		else tous_les_sousmots(reference, argv[2]);
	}
	

	else if ((!strcmp(argv[1],"-x"))&&(argc==3)) {
	        init_automate(&autom);
	        dummy=lit_fichier(argv[2], &autom);  
		ecrit_automate(stdout, &autom);
	}


	else {
	        fprintf(stdout, "\n\n\n\nNOM");
	        fprintf(stdout, "\n     sousmot - outil de recherche de sousmots ");

	        fprintf(stdout, "\n\nDESCRIPTION");
	        fprintf(stdout, "\n     Projet d'Algorithmique - Licence Informatique, UMLV (FRANCE)");
	        fprintf(stdout, "\n     Copyright (C) 2000 Daniele Raffo  <draffo@ken.univ-mlv.fr>");

 	        fprintf(stdout, "\n\nSYNOPSIS");
	        fprintf(stdout, "\n     sousmot [ -x fichier ] | [ -s mot [ reference ]] |");
	        fprintf(stdout, "\n          [ -e fichier1 fichier2 ] | [ -m mot1 mot2 [ reference ]] |");
	        fprintf(stdout, "\n          [ -h ]");

 	        fprintf(stdout, "\n\nOPTIONS");
	        fprintf(stdout, "\n     Les options suivantes sont supportees:");
 
	        fprintf(stdout, "\n\n     -x             Affiche sur stdout l'automate decrit sur fichier.");
 
	        fprintf(stdout, "\n\n     -s             Affiche sur stdout la liste des sousmots du mot.");
	        fprintf(stdout, "\n                    Si defini, la liste sera place' dans le fichier");
	        fprintf(stdout, "\n                    reference.");
 
	        fprintf(stdout, "\n\n     -e             Teste l'equivalence des deux automates decrits");
	        fprintf(stdout, "\n                    dans fichier1 et fichier2. Le code de retour est");
	        fprintf(stdout, "\n                    0 pour deux automates equivalents et 1 pour deux");
	        fprintf(stdout, "\n                    automates non equivalents.");
 
	        fprintf(stdout, "\n\n     -m             Affiche sur stdout la liste des plus petits");
	        fprintf(stdout, "\n                    sousmots qui separent mot1 et mot2. Si defini, la");
	        fprintf(stdout, "\n                    liste sera place' dans le fichier reference.");
 
	        fprintf(stdout, "\n\n     -h             Montre cette aide.");
 
	        fprintf(stdout, "\n\n     Sans parametres, le programme sera lance' en mode interactive.\n\n\n");
	}                                                                     

}










/* Initialisation du modele de donnees utilise' pour l'automate.  */  

void init_automate (automate *a)
{

	int i, j, k;


	for (i=0;i<2*MAX_ETATS;i++) {
		a->status[i]=-1;
		for (j=0;j<MAX_ALPHA;j++)
			for (k=0;k<MAX_TRANS;k++)
				a->table[i][j][k]=-1;
	}

}




/* Lit un fichier d'automate et le memorise dans le modele passe' en parametre, 
/* eventuellement apres un premier automate si celui-la' est deja' dans le modele.
/* Retourne le nombre d'etats de l'automate lu.  */

int lit_fichier(char *afile, automate *a) 
{

	void error(int erreur, int datanum, const char *datastr);

	FILE *fp;
	int n_etats, e, z, decalage;
	char y1, y2, y4, y5; int y3, y6;


        decalage=0; while (a->status[decalage]!=-1 && decalage<MAX_ETATS) decalage++;
			/* trouve le premier emplacement libre pour memoriser l'automate
			/* ca sert au cas ou' on veut memoriser deux automates dans le meme modele */

	if ((fp=fopen(afile, "r"))==0) error(3, 0, afile);


	fscanf(fp, "%d\n", &n_etats);	  /* lecture de la premiere ligne: nombre d'etats */
	e=0;
	while (TRUE) {
		if (e==n_etats) break;
		if (e==MAX_ETATS) error(1, 0, NULL);
	        fscanf(fp, "%c", &y1);	  /* lecture du type d'etat */
	        if (y1=='+') a->status[e+decalage]=2; 
		else if (y1=='-') a->status[e+decalage]=0; 
		else {
		        fclose(fp); error(4, e, afile);
		}
	        fscanf(fp, "%c", &y2);	  /* lecture du fin de ligne ou d'une lettre */
		if (y2=='\n') {
		        e++; continue;
		}
		fscanf(fp, ",%d", &y3);	  /* lecture de la virgule et de l'etat d'arrivee */
		/* les 4 lignes suivantes ajoutent l'etat d'arrivee dans la premiere place vide de la table */
		z=0; 
		while (a->table[e+decalage][(int)y2][z]!=-1) {
		        z++; if (z==MAX_TRANS) {
			        fclose(fp); error(2, 0, NULL);
			}
		}     
		a->table[e+decalage][(int)y2][z]=y3+decalage;    
		while (TRUE) { 
	        	fscanf(fp, "%c", &y4);	/* lecture du pointvirgule ou de la fin de ligne */
        		if (y4=='\n') {
			        e++; break;
			} 
			else if (y4==';') {
			        /* do nothing */
			} 
			else {
			        fclose(fp); error(4, e, afile);
			}
        		fscanf(fp, "%c,%d", &y5, &y6);	/* lecture d'une transition complete */
			z=0; 
			while (a->table[e+decalage][(int)y5][z]!=-1) {
			        z++; if (z==MAX_TRANS) {
				        fclose(fp); error(2, 0, NULL);
				}
			}
			a->table[e+decalage][(int)y5][z]=y6+decalage;
		}
	}
	fclose(fp);
	a->status[0+decalage]+=1;  	/* transforme en initial l'etat 0 */
	return(n_etats);
	
}




/* Ecrit l'automate sur l'ecran ou sur fichier, selon le pointeur a' fichier passe' en parametre.  */ 

void ecrit_automate(FILE *fp, const automate *a)
{

        int n_etats;
	int i, j, k, e, h, hh;
	char *str_status; 


	n_etats=0; while (a->status[n_etats]!=-1 && n_etats<MAX_ETATS) n_etats++;
						/* trouve le nombre d'etats de l'automate */ 


	if (fp==stdout) {

	        /* affichage de l'automate a' l'ecran */

	        fprintf(stdout, "\n\nAUTOMATE A' %d ETATS \n", n_etats);
		for (i=0;i<n_etats;i++) { 
		        switch(a->status[i]) {
			        case 0: str_status="           "; break;
			        case 1: str_status=" (Initial) "; break;
			        case 2: str_status=" (Terminal)"; break;
			        case 3: str_status=" (InitTerm)"; break;
			}

			fprintf(stdout, "\nEtat %2d%s:  ", i, str_status);
			for (j=0;j<MAX_ALPHA;j++) {
			        if (a->table[i][j][0]!=-1) fprintf(stdout, "--%c--> ", (char)j);
				for (k=0;a->table[i][j][k]!=-1;k++) fprintf(stdout, "%d ", a->table[i][j][k]);
				if (a->table[i][j][0]!=-1) fprintf(stdout, "    ");
			}
		}

	printf("\n");
	}


	if (fp!=stdout) {

	        /* ecriture de l'automate sur fichier */

		fprintf(fp, "%d\n", n_etats);            /* ecrit le nombre d'etats */

		for (e=0;e<n_etats;e++) {
	                /* ecrit la ligne correspondante a' l'etat e */ 
		        if (a->status[e]>=2) fprintf(fp, "+"); else fprintf(fp, "-");
		        for (h=0;h<MAX_ALPHA;h++) 
		                if (a->table[e][h][0]!=-1) {
			                fprintf(fp, "%c,%d", (char)h, a->table[e][h][0]);
					break;
				}
			for (hh=h+1;hh<MAX_ALPHA;hh++) 
		                if (a->table[e][hh][0]!=-1) 
			                fprintf(fp, ";%c,%d", (char)hh, a->table[e][hh][0]);
			fprintf(fp, "\n");    
		}
		fclose(fp);

	}


	return;  

}




/* Gere les situations d'erreur. 
/* Les parametres sont le type d'erreur et des informations additionnelles.  */

void error(int erreur, int datanum, const char *datastr)
{

	fprintf(stderr, "\nErreur: ");

	switch(erreur) {
		case 1: fprintf(stderr, "automate trop grand (max %d etats)", MAX_ETATS); 
			break;
		case 2: fprintf(stderr, "trop de transitions pour une meme lettre depuis un meme etat ");
		        fprintf(stderr, "(max %d transitions)", MAX_TRANS);
			break; 
		case 3: fprintf(stderr, "impossible d'ouvrire le fichier %s pour lecture", datastr);
			break;
		case 4: fprintf(stderr, "fichier %s malforme' dans l'etat %d, ligne %d", datastr, datanum, datanum+2);
			break;
		case 5: fprintf(stderr, "impossible d'ecrire le fichier %s", datastr);
			break;
	        case 6: fprintf(stderr, "mot %s trop long (max %d characteres)", datastr, MAX_L_MOT);
		        break;
	        case 7: fprintf(stderr, "l'automate %s n'est pas complet", datastr);
		        break;
	        case 8: fprintf(stderr, "les transitions des deux automates ne sont pas definis sur le meme langage");
		        break;
	}

	fprintf(stderr, "\n\n"); exit(-erreur);

}




/* Verifie si un automate est complet.  */

int est_complet(const automate *a)
{

	int n_etats, i, j;
       

	n_etats=0; while (a->status[n_etats]!=-1 && n_etats<MAX_ETATS) n_etats++;
						/* trouve le nombre d'etats de l'automate */ 

	for (j=0;j<MAX_ALPHA;j++) 
	        for (i=1;i<n_etats;i++) {
			if ((a->table[i][j][0]==-1)&&(a->table[0][j][0]!=-1)) return(FALSE);
			if ((a->table[0][j][0]==-1)&&(a->table[i][j][0]!=-1)) return(FALSE);
		}

	return(TRUE); 

}




/* Teste si le deux AFD complets lequel fichiers sont passes en parametre reconnaissent le meme langage. 
/* Retourne 0 s'ils sont equivalents, 1 s'ils ne le sont pas.  */ 

int equiv_automate(char *afile1, char *afile2)
{

	int lit_fichier(char *afile, automate *a);
	void init_automate(automate *a);
	void ecrit_automate(FILE *fp, const automate *a);
	void equiv(int e1, int e2, const automate *a, int classe[]);
	int est_complet(const automate *a);

	automate atest;
	int classe[2*MAX_ETATS];
	int start2, tot_etats;
	int i, p, q;

	
	init_automate(&atest);
	/* lit les fichiers des deux automates et memorise ces derniers dans un meme modele, 
	/* l'un apres l'autre, avec conseguente renumerotation des etats du deuxieme automate */
	start2=lit_fichier(afile1, &atest);
	if (!est_complet(&atest)) error(7, 0, afile1);            /* teste si le premier automate est complet */
	init_automate(&adummy);
	dummy=lit_fichier(afile2, &adummy);
	if (!est_complet(&adummy)) error(7, 0, afile2);           /* teste si le deuxieme automate est complet */  
	tot_etats=start2+lit_fichier(afile2, &atest);
	if (!est_complet(&atest)) error(8, 0, NULL);              /* teste si le deux automates ont les etiquettes
								  /* des transitions definies sur un meme langage, 
								  /* en testant si l'automate globale est complet  */
	/* le premier automate commence a' atest->table[0][][], le deuxieme a' atest->table[start2][][] */
	if (TRACEON) ecrit_automate(stdout, &atest);


	for (i=0;i<tot_etats;i++) classe[i]=i;		/* initialisation des classes */
	equivhalt=FALSE;
	equiv(0, start2, &atest, classe);
		/* l'algorithme est appele' en lui passant d'abord les etats initiaux des deux automates */
	if (equivhalt) return(1); else return(0);
	
}




/* Algorithme recursif pour tester l'equivalence de deux AFD complets,
/* memorises l'un apres l'autre dans le modele passe' en parametre.
/* e1 et e2 sont deux etats des automates 1 et 2.
/* On utilise une variable globale (equivhalt) comme flag pour la condition de non-equivalence, 
/* pour eviter des problemes lies au retour des valeurs.  */

void equiv(int e1, int e2, const automate *a, int classe[])
{

        int tot_etats;
	int x, y, n, l, t;


	if (equivhalt) return;
        tot_etats=0; while (a->status[tot_etats]!=-1 && tot_etats<MAX_ETATS) tot_etats++;      
	                                        /* trouve le nombre d'etats total des deux automates */
	if (TRACEON) { 
	        fprintf(stdout, "\n--------------------------------------------------");
		fprintf(stdout, "\nFN APPELEE AVEC PARAMS: (%d, %d)", e1, e2);
		fprintf(stdout, "\n  ETAT "); for (t=0;t<tot_etats;t++) fprintf(stdout, "%2d ", t);		
	        fprintf(stdout, "\nCLASSE "); for (t=0;t<tot_etats;t++) fprintf(stdout, "%2d ", classe[t]);
		fprintf(stdout, "\nSTATUS "); for (t=0;t<tot_etats;t++) fprintf(stdout, "%2d ", a->status[t]);
	}

	if ((a->status[e1]>=2 && a->status[e2]<2) || (a->status[e2]>=2 && a->status[e1]<2)) equivhalt=TRUE; 
        /* si un des etats e1 et e2 est terminal et l'autre pas, les deux automates ne sont pas equivalents */
	x=classe[e1], y=classe[e2];
	if (x!=y) {             
	        for (n=0;n<tot_etats;n++) if (classe[n]==y) classe[n]=x; 
                /* fait l'union des classes de e1 et de e2 */ 	  
		for (l=0;l<MAX_ALPHA;l++)
		        if (a->table[e1][l][0]!=-1)      
                                equiv(a->table[e1][l][0], a->table[e2][l][0], a, classe);
	}

}




/* Retourne un automate deterministe complet qui reconnait tous les sousmots du mot passe' en parametre.  */

automate automate_sousmots(const char mot[]) 
{

 	void init_automate(automate *a);

        int temp[MAX_L_MOT+2][MAX_L_MOT];       /* table temporaire des transitions pour le traitement du mot */
	automate as;
    	int longueur_mot, n_etats, poubelle, lettres_diff;
	int n, i, u, v, w, j, k, h;
	const int NONVALIDE=MAX_L_MOT+5;


	if (strlen(mot)>MAX_L_MOT) error(6, 0, mot);


	for (longueur_mot=0;mot[longueur_mot]!='\0';longueur_mot++) ;   /* trouve le nombre de lettres du mot */
	n_etats=longueur_mot+2;    /* nombre d'etats de l'automate */
	poubelle=n_etats-1;        /* nombre de l'etat poubelle (c'est le dernier etat) */


	/* remplissage de la table temporaire */
	for (n=0;n<n_etats;n++) 
 	        for (i=0;i<longueur_mot;i++) {
                        if (i>=n) temp[n][i]=i+1; 
			else temp[n][i]=poubelle;
		}

	if (TRACEON) {
	        fprintf(stdout, "\n\n    "); 
                for (u=0;u<longueur_mot;u++) 
		        fprintf(stdout, " %c ", mot[u]);
	        for (v=0;v<n_etats;v++) {
		        fprintf(stdout, "\n%2d: ", v); 
			for (w=0;w<longueur_mot;w++) fprintf(stdout, "%2d ", temp[v][w]);
		}
	}


	/* fusionnement des colonnes correspondantes aux lettres identiques */
	lettres_diff=longueur_mot;               /* nombre de lettres differentes dans le mot */
	for (j=0;j<longueur_mot-1;j++) 
	        for (k=j+1;k<longueur_mot;k++) 
		        if ((mot[k]==mot[j])&&(temp[0][k]!=NONVALIDE)) {     
                                /* si on a trouve' deux lettres identiques non encore traitees */ 
			        for (h=0;h<n_etats;h++) {
				        if (temp[h][k]<temp[h][j]) temp[h][j]=temp[h][k];  /* fallthrough */ 
					temp[h][k]=NONVALIDE;   
					/* la colonne correspondante a' une lettre deja' existante 
					/* est marque' comme NONVALIDE, en substituant tous ses valeurs */
				}
				lettres_diff--;             
			}

	if (TRACEON) {
      	        fprintf(stdout, "\n\n    "); 
                for (u=0;u<longueur_mot;u++) fprintf(stdout, " %c ", mot[u]); 
	        for (v=0;v<n_etats;v++) {
		        fprintf(stdout, "\n%2d: ", v); 
                        for (w=0;w<longueur_mot;w++) {
			        if (temp[0][w]!=NONVALIDE) fprintf(stdout, "%2d ", temp[v][w]);
				else fprintf(stdout, "NV ");
			}			
		}
	        fprintf(stdout, "\n\n    "); 
		for (u=0;u<longueur_mot;u++) if (temp[0][u]!=NONVALIDE) fprintf(stdout, " %c ", mot[u]);
     	        for (v=0;v<n_etats;v++) {
		        fprintf(stdout, "\n%2d: ", v); 
			for (w=0;w<longueur_mot;w++) 
                                if (temp[0][w]!=NONVALIDE) fprintf(stdout, "%2d ", temp[v][w]);
		}
		fprintf(stdout, "\n\n%d LETTRES DIFFS SUR %d \n\n", lettres_diff, longueur_mot); 
	}


	/* copie des donnees dans un modele d'automate */
	init_automate(&as);
	for (j=0;j<n_etats;j++) 
	        for (k=0;k<longueur_mot;k++)  
                        if (temp[0][k]!=NONVALIDE) as.table[j][(int)(mot[k])][0]=temp[j][k];
		        /* on saute les occurrences suivantes d'une meme lettre
			/* en excluant les colonnes du table qui ont le premier element NONVALIDE */ 
	for (j=0;j<n_etats-1;j++) as.status[j]=2; 
	as.status[0]=3; 
	as.status[poubelle]=0;


	return(as);

}




/* Lit depuis un automate des sousmots et sa liste des sousmots liste_lecture
/* pour ecrire dans liste_ecriture les sousmots de longueur immediatement superieure.  */  

void sousmots(const automate *a, liste_sousmots *liste_lecture, liste_sousmots *liste_ecriture)
{

	void init_liste(liste_sousmots *liste);

	int n_etats, poubelle;
	int transition;                   /* etat d'arrivee apres avoir lu la lettre n */
	int index_lect=0;                 /* index pour la liste_lecture */ 
	int index_ecr=0;                  /* index pour la liste_ecriture */
	int suffix;                       /* fin du sousmot: on ajoutera ici n, la derniere lettre */
	int n;


	n_etats=0; while (a->status[n_etats]!=-1 && n_etats<MAX_ETATS) n_etats++;
						/* trouve le nombre d'etats de l'automate */ 
	poubelle=n_etats-1;


	init_liste(liste_ecriture);

	if (liste_lecture[0].terminus==-1) {
	        /* il n'y a pas encore une liste_lecture; ecriture des sousmots de longueur 1 */
		for (n=0;n<MAX_ALPHA;n++) {
		        transition=a->table[0][n][0];
		        if ((transition!=-1)&&(transition!=poubelle)) {
		                liste_ecriture[index_ecr].sousmot[0]=(char)n;
				liste_ecriture[index_ecr].sousmot[1]='\0';
				liste_ecriture[index_ecr].terminus=transition;
				index_ecr++;
			}
		}
	}
	
	else {
	        /* ecriture des sousmots obtenus a' partir de ceux de la liste_lecture */
	        for (;liste_lecture[index_lect].terminus!=-1;index_lect++) { 
		        for (n=0;n<MAX_ALPHA;n++) {
			        transition=a->table[(liste_lecture[index_lect].terminus)][n][0];
				if ((transition!=-1)&&(transition!=poubelle)) {
		                        strcpy(liste_ecriture[index_ecr].sousmot, liste_lecture[index_lect].sousmot);
					suffix=strlen(liste_ecriture[index_ecr].sousmot);
					liste_ecriture[index_ecr].sousmot[suffix]=(char)n;
					liste_ecriture[index_ecr].sousmot[suffix+1]='\0';
				        /* ajoute la lettre de chaque transition au sousmot lu
					/* pour obtenir un sousmot de longueur majore' de 1 */  
		                        liste_ecriture[index_ecr].terminus=transition;
					index_ecr++;
				}
			}
		}
	}


	return;

}




/* Initialise la liste des sousmots.  */

void init_liste(liste_sousmots *liste)
{

        int i;


	for (i=0; i<DIM_LISTE; i++) {
	        strcpy(liste[i].sousmot, "\0"); 
	        liste[i].terminus=-1;
		liste[i].unique=TRUE;
	}

}
	
	


/* Ecrit tous les sousmots du mot sur le pointeur a' fichier fp.  */ 

void tous_les_sousmots(FILE *fp, const char *mot_a_traiter)
{

	void init_liste(liste_sousmots *liste);
	automate automate_sousmots(const char mot[]);
	void sousmots(const automate *a, liste_sousmots *liste_lecture, liste_sousmots *liste_ecriture); 

        automate amot;
        liste_sousmots liste_lect[DIM_LISTE];
        liste_sousmots liste_ecr[DIM_LISTE];
	int l, m, c, count=0;


	if (strlen(mot_a_traiter)>MAX_L_MOT) error(6, 0, mot_a_traiter);

	init_automate(&amot);
	init_liste(liste_lect); init_liste(liste_ecr);
	amot=automate_sousmots(mot_a_traiter);


	if (TRACEON) fprintf(stdout, "\n     SOUSMOT           TERMINUS");	
	for (l=1;l<=strlen(mot_a_traiter);l++) {                           
                /* trouve les sousmots de longueur l */
	        sousmots(&amot, liste_lect, liste_ecr);
	        for (m=0;liste_ecr[m].terminus!=-1;m++) {
		        if (TRACEON)
	       	                fprintf(stdout, "\n%3d) %-16s  %2d", ++count, liste_ecr[m].sousmot, liste_ecr[m].terminus);
			if ((!TRACEON)||((TRACEON)&&(fp!=stdout)))
			        fprintf(fp, "%s\n", liste_ecr[m].sousmot);
		}
				
		/* la vieille liste d'ecriture des sousmots de longueur l devient la liste de lecture
		/* qui servira a' la creation des sousmots de longueur l+1 */
		for (c=0;c<DIM_LISTE;c++) {       
		        liste_lect[c]=liste_ecr[c];
		}
		init_liste(liste_ecr);
	}


	return;

} 




/* Ecrit la liste des plus petits sousmots qui separent mot1 et mot2 sur le pointeur a' fichier fp.  */

void distingue(FILE *fp, const char *mot1, const char *mot2)
{
 
	void init_liste(liste_sousmots *liste);
	automate automate_sousmots(const char mot[]);
	void sousmots(const automate *a, liste_sousmots *liste_lecture, liste_sousmots *liste_ecriture); 

	automate amot1, amot2;
        liste_sousmots liste_lect1[DIM_LISTE], liste_ecr1[DIM_LISTE];
        liste_sousmots liste_lect2[DIM_LISTE], liste_ecr2[DIM_LISTE];
	int separateurs=FALSE, unique=TRUE;
	int l, m1, m2, i;


	if (strlen(mot1)>MAX_L_MOT) error(6, 0, mot1);
	if (strlen(mot2)>MAX_L_MOT) error(6, 0, mot2);  

	init_liste(liste_lect1); init_liste(liste_ecr1);
	init_liste(liste_lect2); init_liste(liste_ecr2);
	amot1=automate_sousmots(mot1);
	amot2=automate_sousmots(mot2);
 

	if (!strcmp(mot1, mot2)) return;     /* si le mots sont egaux, on ne fait meme pas demarrer l'algorithme */

	for (l=1;l<=(strlen(mot1)>strlen(mot2)?strlen(mot1):strlen(mot2));l++) {                           

                /* trouve les sousmots de longueur l des deux mots */
	        sousmots(&amot1, liste_lect1, liste_ecr1);
	        sousmots(&amot2, liste_lect2, liste_ecr2);

		/* fait la separation entre le deux groupes de sous mots */
		if (TRACEON) fprintf(stdout, "TEST GROUPE DE LONGUEUR %d ...\n", l);
	        for (m1=0;liste_ecr1[m1].terminus!=-1;m1++) {
		        unique=TRUE;
         		for (m2=0;liste_ecr2[m2].terminus!=-1;m2++) {
			        if (!strcmp(liste_ecr1[m1].sousmot, liste_ecr2[m2].sousmot)) {
				        liste_ecr2[m2].unique=FALSE; 
					unique=FALSE; 
					break; 
				}
			}
			if (unique) {
			        separateurs=TRUE; 
				fprintf(fp, "%s\n", liste_ecr1[m1].sousmot); 
			}
		}
		for (m2=0;liste_ecr2[m2].terminus!=-1;m2++) {
		        if (liste_ecr2[m2].unique) {
			        separateurs=TRUE;
			        fprintf(fp, "%s\n", liste_ecr2[m2].sousmot); 
			}
		}


		/* si separateurs=TRUE, on a trouve' des sous-mots qui distinguent,
		/* sinon il faut faire un autre tour avec les sousmots de longueur l+1 */
		if (separateurs) return;
			
		/* fait la copie de liste_ecriture sur la liste_lecture et initialise les flags d'unicite' des sousmots */
		for (i=0;i<DIM_LISTE;i++) {       
		        liste_lect1[i]=liste_ecr1[i];
			liste_lect1[i].unique=TRUE;
		        liste_lect2[i]=liste_ecr2[i];
		        liste_lect2[i].unique=TRUE;
		}
		init_liste(liste_ecr1);
		init_liste(liste_ecr2);
	}
     

	return;

}




/* Demande la peripherique d'output pour l'envoi du resultat de l'elaboration.  
/* Retourne TRUE pour output sur ecran, FALSE pour output sur fichier.  */

int output_sur_ecran(void)
{

        char c;


        fprintf(stdout, "Affichage a' l'ecran ou ecriture sur fichier (e/f): "); 
	fflush(stdin); scanf("%c", &c);
	printf("\n");
	return(c!='f');

}



/* END OF FILE */