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

#define MAXLEN 5000
#define MAXNUM 200

int lcslen(char *x, char *y);

int main(int argc, char *argv[]) {
	FILE *fp;
	char buffer[MAXLEN];
	char *data[MAXNUM];
	int result[MAXNUM][MAXNUM];
	int i, j, num, len;
	
	/* check arguments */
	if (argc < 2) {
		printf("Usage: %s input_file\n", argv[0]);
		return 1;
	}

	/* open input file */
	fp = fopen(argv[1], "r");
	if (fp == NULL) {
		printf("Can't read this file.\n");
		return 1;
	}

	/* load data */
	num = 0;
	while (!feof(fp)) {
		memset(buffer, 0, MAXLEN);
		fgets(buffer, MAXLEN, fp);
		len = strlen(buffer);
		
		if (len == 0) break;
		if (buffer[len-1] == '\n') {
			buffer[len-1] = '\0';
		}
		
		data[num] = strdup(buffer);
		num++;
	}
	fprintf(stderr, "%d lines loaded.\n", num);
	
	/* initalize LCS matrix
	for (i = 0; i < num; i++) {
		for (j = 0; j < num; j++) {
			result[i][j] = 0;
		}
	} */
	
	/* compute LCS matrix */
	for (i = 0; i < num; i++) {
		for (j = i; j < num; j++) {
			result[i][j] = lcslen(data[i],data[j]);
			if (i != j) {
				result[j][i] = result[i][j];	
			}
		}
		if ((i+1) % 10 == 0) fprintf(stderr,"..%d",i+1);
	}

	/* output */
	for (i = 0; i < num; ++i) {
		for (j = 0; j < num; ++j) {
			printf("%d ", result[i][j]);
		}
		printf("\n");
	}

	/* for MATLAB
	printf("[");
	for (i = 0; i < num; ++i) {
		for (j = 0; j < num; ++j) {
			printf("%d ", result[i][j]));
		}
		printf(";");
	}
	printf("]\n");
	*/

	/* for TeX
	for (i = 0; i < num; ++i) {
		for (j = 0; j < num; ++j) {
			printf("%d & ", result[i][j]));
		}
		printf("\\\\\n");
	} */

	return 0;
}

/* compute LCS-length */
int lcslen(char *x, char *y) {
	int m, n, res;
	int i, j;
	int **c;
	
	m = strlen(x);
	n = strlen(y);

	/* allocate & initialize array */
	c = (int **)malloc(sizeof(int *)*(m+1));
	for (i = 0; i < m+1; ++i) {
		c[i] = (int *)malloc(sizeof(int)*(n+1));
	}
	for (i = 0; i <= m; ++i) {
		c[i][0] = 0;
	}
	for (j = 0; j <= n; ++j) {
		c[0][j] = 0;
	}

	/* DP */
	for (i = 1; i <= m; ++i) {
		for (j = 1; j <= n; ++j) {
			if (x[i-1] == y[j-1]) {
				c[i][j] = c[i-1][j-1] + 1;
			} else {
				c[i][j] = (c[i-1][j] > c[i][j-1]) ? c[i-1][j] : c[i][j-1];
			}
		}
	}
	
	res = c[m][n];

	for (i = 0; i < m+1; ++i) {
		free(c[i]);
	}
	free(c);

	return res;
}