/* Problem 5--Before and After
   This is what I call a "parse problem."  Once you get the data read in
   properly, it's not too hard to process it properly to get the right
   answer.  No limit is given for the number of lines, so I use a linked
   list to maintain the information.  There were certain ambiguities
   in this question.  In particular, the problem doesn't state what
   happens if two phrases match in more than one way.  This solution
   prints out all matches. */

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

typedef char Word[15];
typedef Word Line[50]; /* A line is simply an array of words */
typedef struct LineList { /* Linked list of lines */
 Line l;
 struct LineList *next;
} LineList;

int main (int argc, char **argv);
void ReadIn (void);
void Cleanup (LineList *Data);
void compare (Line A, Line B);

FILE *in, *out;
LineList *Data=NULL;

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

  LineList *P, *Q;

 in = fopen ("prob5.in","r");
 out = fopen ("prob5.out","w");
 ReadIn ();
 for (P = Data; P != NULL; P = P->next) /* Process each pair */
  for (Q = Data; Q != NULL; Q = Q->next) {
   if (P==Q) continue; /* We don't compare a phrase against itself */
   compare (P->l,Q->l);
 }
 Cleanup (Data);
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* ReadIn reads in the data to our linked list of lines */
void ReadIn (void) {

  LineList *P = NULL;
  int wct;
  char *nextword;
  char line[60];

 while (1) {
  fgets (line,sizeof line, in);
  if (line[0]=='\n') break;
  line[strlen(line)-1]=0;
  if (P==NULL)  /* first line */
   P = Data = malloc (sizeof (LineList));
  else /* subsequent line */
   P = P->next = malloc (sizeof (LineList));
  P->next = NULL;
  wct = 0;
  nextword = strtok (line," "); /* strtok takes will separate the */
  while (nextword != NULL) {    /* input line by words */
   if (strlen (nextword)==0) {nextword = strtok (NULL," ");continue;}
   strcpy (P->l[wct++],nextword);/* copy the word into the line */
   nextword = strtok (NULL, " ");
  }
  strcpy (P->l[wct],""); /* terminate with an empty word */
 }
}

/* Cleanup dellocates all the space */
void Cleanup (LineList *Data) {

 if (Data != NULL) {
  Cleanup (Data->next);
  free (Data);
 }
}

/* compare takes two lines and prints out all matches */
void compare (Line A, Line B) {

  int bstrt, i, DONE, gap;

 for (bstrt=0; strcmp (A[bstrt],"") != 0; bstrt++) {
  DONE = 0; /* we go through B and match it word-by-word with A */
  for (i=bstrt; strcmp (A[i],"")&& !DONE; i++) { /* starting at bstrt*/
   DONE = strcmp (B[i-bstrt],"")==0 || strcmp (A[i],B[i-bstrt]);}
  if (DONE) continue;
  gap = 0; /* we have a match */
  for (i=0; strcmp (A[i],"") != 0; i++) { /* print first line */
   fprintf (out,"%s ",A[i]);
   if (i < bstrt) gap += strlen (A[i])+1;/*compute leading spaces*/
  }
  fprintf (out,"\n");
  for (i=0; i<gap;i++) fprintf (out," ");/* print leading spaces */
  for (i=0; strcmp (B[i],"") != 0; i++)/* print second line */
   fprintf (out,"%s ",B[i]);
  fprintf (out,"\n\n");
 }
}