/* File: sma1.c
 * Author: Thierry Lecroq
 * Affiliation: University of Rouen, LITIS EA 4108
 * E-Mail: Thierry.Lecroq@univ-rouen.fr
 */

#include <stdio.h>

#define MAXSIZE 10
#define FIRSTLETTER 'a'
#define LASTLETTER  'z'
#define DELTA(q,c) trans[(q)][(c)-FIRSTLETTER]


/******************************************************************
 * Construction of the string matching automaton of x of length m *
 ******************************************************************/
int **smaComplete(char *x, int m, int asize) {
   int stateNb, i, q0, r, t, p;
   int **trans;

   trans = (int **)malloc((m+1)*sizeof(int *));
   for (i = 0; i <= m; ++i)
      trans[i] = (int *)calloc(asize, sizeof(int));
   q0 = 0;
   stateNb = 1;
   t = q0;
   for (i = 0; i < m; ++i) {
      p = stateNb++;
      r = DELTA(t,x[i]);
      DELTA(t,x[i]) = p;
      memcpy(trans[p], trans[r], asize*sizeof(int));
      t = p;
   }
   return trans;
}


/****************************
 * Draw the whole automaton *
 ****************************/
void aut2tex(char *x, int m, int asize, int **trans) {
   char fileName[MAXSIZE];
   FILE *FOUT;
   int i, j, q;
   char c;

   strcpy(fileName, x);
   strcat(fileName, ".tex");
   FOUT = fopen(fileName, "w");
   fprintf(FOUT, "\\documentclass{beamer}\n");
   fprintf(FOUT, "\\usepackage{tikz}\n");
   fprintf(FOUT, "\\usefonttheme[onlymath]{serif}\n");
   fprintf(FOUT, "\\tikzstyle{myState}=[draw=blue!50,very thick,fill=blue!20,circle,inner sep =1pt]\n");
   fprintf(FOUT, "\\def\\boundb{(-3,3.5) rectangle (8,-3)}\n");
   fprintf(FOUT, "\\begin{document}\n");
   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{String Matching Automaton of $%s$}\n", x);
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   for (i = 0; i <= m; ++i) {
      fprintf(FOUT, "\\node[myState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
   }
   fprintf(FOUT, "\\path[->]\n");
   for (i = 0; i < m+1; ++i) {
      for (j = 0; j < asize; ++j) {
	 c = j+FIRSTLETTER;
         q = DELTA(i, c);
	 if (q == i)
            if (q == 0)
               fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma\\setminus\\{%c\\}$} (q0)\n", x[0]);
            else

               fprintf(FOUT, "(q%d) edge [thick, loop above] node {$%c$} (q%d)\n", i, c, q);
	 else if (q == i+1)
            fprintf(FOUT, "(q%d) edge [thick] node [above] {$%c$} (q%d)\n", i, c, q);
	 else
            fprintf(FOUT, "(q%d) edge [thick, bend left = 75] node [above] {$%c$} (q%d)\n", i, c, q);
      }
   }
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");
   fprintf(FOUT, "\\end{frame}\n");
   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{Please cite}\n");
   fprintf(FOUT, "\\textit{Algorithms on strings}\n\n");
   fprintf(FOUT, "M. Crochemore, C. Hancart and T. Lecroq\n\n");
   fprintf(FOUT, "Cambridge University Press, 2007\n\n");
   fprintf(FOUT, "\\end{frame}\n");
   fprintf(FOUT, "\\end{document}\n");
   fclose(FOUT);
}


/********
 * Main *
 ********/
int main(int argc, char *argv[]) {
   char x[MAXSIZE];
   int asize, i, m;
   char c;
   int **trans;

   if (argc != 2) {
      printf("usage: %s string\n", argv[0]);
      exit(1);
   }
   strcpy(x, argv[1]);
   m = strlen(x);
   if (m > MAXSIZE-1) {
      printf("String length should not exceed %d\n", MAXSIZE-1);
      exit(1);
   }
   asize = 0;
   for (i = 0; i < m; ++i) {
      if (x[i] < FIRSTLETTER || x[i] > LASTLETTER) {
	 printf("Letters should be within %c and %c\n", FIRSTLETTER, LASTLETTER);
         exit(1);
      }
      if (x[i]-FIRSTLETTER+1 > asize) asize = x[i]-FIRSTLETTER+1;
   }
   trans = smaComplete(x, m, asize);
   aut2tex(x, m, asize, trans);
}