/*--------------------------------------------------------------------
 *
 *   csc 148s, 1997, Assignment 0: String Matching
 *   name:            >> Your name here <<
 *   student number:  >> Your student number here <<
 *   lecturer:        >> Your lecturer's name <<
 *   tutor:           >> Your tutor's name <<
 *    This program reads in two strings and finds the longest substring
 * common to both.  Output consists of a message indicating the length
 * and position of the longest common substring.  If _no_ substring is
 * common to both, a message indicating this is printed instead.
 *    In the case of a tie, the substring closest to the beginning of
 * the first string is chosen.  If this also yields a tie (because that
 * substring occurs more than once in the second string), the occurence
 * closest to the beginning of the second string is chosen.
 *
 *--------------------------------------------------------------------
 */

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

/* Maximum number of columns and rows in the incidence matrix to be built.
   These also determine the maximum length of input string that the
   program can handle. */
#define MAXROWS 20
#define MAXCOLS 20

#define FALSE 0
#define TRUE 1
typedef int boolean;



/* buildMatrix
 *--------------------------------------------------------------------
 * Given two strings s1 and s2, builds an incidence matrix for them,
 * called IM.
 * Preconditions: MAXROWS >= strlen(s1)
 *                MAXCOLS >= strlen(s2)
 *                s1 and s2 have values
 */

void
buildMatrix (char *s1, char *s2, boolean IM[MAXROWS][MAXCOLS])
{
    /* Fill in the body of this function. */
}



/* checkOneDiagonal
 *--------------------------------------------------------------------
 * Checks for a sequence of trues along a single diagonal in IM, starting at
 * position (startRow, startCol).  If a sequence is found that is longer than
 * maxSoFar, the upper-leftmost (i,j) origin of that sequence is returned and
 * maxSoFar is updated.  
 *    Note that there could be several stretches of trues along this one
 * diagonal to be checked.
 * Preconditions: IM has values in rows 0..numRows-1 and
 *                                 columns 0..numCols-1
 *                0 <= startRow <= numRows
 *                0 <= startCol <= numCols
 *                maxSoFar has a value
 */

void
checkOneDiagonal (boolean IM[MAXROWS][MAXCOLS], int startRow, int startCol,
		  int *maxSoFar, int *i, int *j, int numRows, int numCols)
{
    /* Fill in the body of this function. */
}
	    


/* findLongestSequence
 *--------------------------------------------------------------------
 * Finds the longest sequence of trues along a main diagonal in the incidence
 * matrix IM.  Both the length of this sequence and the (i,j) position of it's
 * upper-left-most origin are returned.  In the case of a tie, the sequence
 * whose origin is nearest row 1 (and if this also yields a tie, then the
 * sequence whose origin is nearest column 1) is the one whose information
 * is returned.  If there are no trues in IM, length is returned as 0.
 * Preconditions: IM has values in rows 0..numRows-1 and 
 *                                 columns 0..numCols-1.
 */

void
findLongestSequence (boolean IM[][], int *lengthOfSeq, int *i, int *j,
		     int numRows, int numCols)
{
    int row, column;
    /* Since we haven't found any sequences of trues yet, lengthofSeq is 0 
       for now. */
    *lengthOfSeq = 0;

    /* Check all diagonals starting in column 0. */
    for(row = numRows-1; row >=0 ; row--)
        checkOneDiagonal (IM, row, 0, lengthOfSeq, i, j, numRows, numCols);

    /* Check all diagonals starting in row 0, except the one in row 0, 
       column 0; it was checked in the first for-loop. */
    for (column = 1; column < numCols; column++)
        checkOneDiagonal (IM, 0, column, lengthOfSeq, i, j, numRows, numCols);

}



/*-----  M a i n   P r o g r a m  ------------------------------------------*/

main()
{
    /* The two strings to be compared.  Two positions are for the \0 that is 
       stored to indicate the end of the string, and the \n from fgets. */
    char s1[MAXROWS+2], s2[MAXCOLS+2];
    int numRows, numCols;
    int sequenceLength, i, j;
    char *result;
    
    /* The incidence matrix itself.
       Doesn't have those extra two positions because we don't need to 
       store \0 or \n in the matrix. */
    boolean IM[MAXROWS][MAXCOLS]; 


    /* First, read in the two strings, s1 and s2.
       Note that they must be on separate lines. */
    if((result = fgets(s1, MAXROWS+2, stdin)) == NULL){
	fprintf(stderr, "ERROR in reading input\n");
	exit(-1);
    }
    if((result = strchr(s1, '\n')) != NULL) {
	*result = '\0';
    } else {
	fprintf(stderr, "The first string was too long for the buffer.\n");
	exit(-1);
    }
    
    if((result = fgets(s2, MAXCOLS+2, stdin)) == NULL){
	fprintf(stderr, "ERROR in reading input\n");
	exit(-1);
    }
    if((result = strchr(s2, '\n')) != NULL) {
	*result = '\0';
    } else {
	fprintf(stderr, "The second string was too long for the buffer.\n");
	exit(-1);
    }
    

    /* Number of rows and columns used in the incidence matrix.  Determined by 
       the length of the two strings. */
    numRows = strlen(s1);
    numCols = strlen(s2);


    /* First, build the incidence matrix.  Then use it to find the longest 
       substring common to the two input strings, and print the results. */
    buildMatrix (s1, s2, IM);
    findLongestSequence(IM, &sequenceLength, &i, &j, numRows, numCols);
    if(sequenceLength == 0) {
	printf("There were no common substrings\n");
    } else {
	printf("The longest common substring has length: %d\n",sequenceLength);
        /* Add 1 to i and j because string indexes start at zero, but
	   humans aren't used to counting from zero. */
	printf("It occurs in string 1 starting at character: %d\n", i+1);
	printf("It occurs in string 2 starting at character: %d\n", j+1);
    }
}