#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define MAX 256

void clear(char **mass, int n)
	{
	int i;

	for(i = 1; i <= n; i++) free(mass[i]);
	free(mass);

	return;
	}
int count(FILE *fp)
	{
	int i = 0;
	char c;

	c = getc(fp);
	while (isspace(c)) c = getc(fp);
	while (c != EOF)
		{
		if (isspace(c) || (c == EOF))
			{
			c = getc(fp);
			i++;
			while (isspace(c)) c = getc(fp);
			}
		if (c != EOF) c = getc(fp);
		}

	return(i);
	}

char **input(FILE *fp, int *k, char **mass)
	{
	char word0[MAX], c;
	int i = 0, j = 0;

	c = getc(fp);
	mass = (char**)malloc((*k+1)* MAX * sizeof(char*));
	while (c != EOF)
		{
		while ((!isspace(c)) && (c != EOF))
			{
			word0[j++] = c;
			c = getc(fp);
			}
		if (j != 0)
			{
			word0[j++] = '\0';
			mass[(++i) * sizeof(char*)] = (char*)malloc(j * sizeof(char));
			strcpy(mass[i * sizeof(char*)],word0);
			/*fprintf(stderr, "%s1\n",mass[i * sizeof(char*)]);*/
			}

		if (c != EOF) c = getc(fp);
		j = 0;
		}
	*k = i;
	/*fprintf(stderr, "%d %d\n",i , k);*/
	/*for(j = 1;j <= k; j++) fprintf(stderr, "%s1\n",mass[j * sizeof(char*)]);*/
	return mass;
	}

void PrintLSC(char *strel, char **f2, int i, int j, int n, int m, int *l,int *pr)

	{
	int k, b, c;

	/*printf("%d %d\n",i,j);*/
	if ((i == 0) && (j != 0)) {printf("-%d\n",j);j = 0;}
	if ((j == 0) && (i != 0)) {for(k = 1;k <= i;k++) printf("+%s\n",f2[k*sizeof(char*)]); i = 0;}
	if ((i != 0) || (j != 0))
		{
		switch (strel[j*(n+1)+i])
			{
			case -1 :
				{
				b = *l;
				*l = 0;
				c = *pr;
				*pr = 0;
				PrintLSC(strel, f2, i - 1, j, n, m, l, pr);
				printf("+%s\n",f2[i*sizeof(char*)]);
				if (b != 0) printf("-%d\n",b);
				if (c != 0) printf("*%d\n",c);
				break;
				}
			case 0 :
				{
				++(*pr);
				b = *l;
				*l = 0;
				PrintLSC(strel, f2, --i, --j, n, m, l, pr);
				if (((i == 0) || (j == 0)) && (*pr != 0)) printf("*%d\n",*pr);
				if (b != 0) printf("-%d\n",b);
				break;
				}
			case 1 :
				{
				++(*l);
				c = *pr;
				*pr = 0;
				PrintLSC(strel, f2, i, --j, n, m, l, pr);
				if (((i == 0) || (j == 0)) && (*l != 0)) printf("-%d\n",*l);
				if (c != 0) printf("*%d\n",c);
				break;
				}
			}
		}
	return;
	}

void LCSLength(char **f1, char **f2, int n, int m)
	{
	int i, j, l = 0, pr = 0, *mass;
	char  *strel;

	mass = (int*)malloc(sizeof(int) * (m + 1) * (n + 1));
	strel = (char*)malloc(sizeof(int) * (m + 1) * (n + 1));
	for(i = 0;i <= n; i++) {mass[i] = 0; strel[i] = 0;}
	for(j = 1;j <= m; j++) {mass[j*(n+1)] = 0; strel[j*(n+1)] = 0;}
	for(j = 1;j <= m; j++)
		{
		for(i = 1;i <= n; i++)
			{
			/*fprintf(stderr, "%s & %s\n",f1[j*sizeof(char*)],f2[i*sizeof(char*)]);*/
			if (!strcmp(f1[j*sizeof(char*)],f2[i*sizeof(char*)]))
				{
				mass[j*(n+1)+i] = mass[(j-1)*(n+1)+i-1] + 1;
				strel[j*(n+1)+i] = 0;
				}
			else if (mass[(j-1)*(n+1)+i] >= mass[j*(n+1)+i-1])
					{
					mass[j*(n+1)+i] = mass[(j-1)*(n+1)+i];
					strel[j*(n+1)+i] = 1;
					}
				else
					{
					mass[j*(n+1)+i] = mass[j*(n+1)+i-1];
					strel[j*(n+1)+i] = -1;
					}
			/*printf("%d %d\n",strel[j*(n+1)+i],mass[j*(n+1)+i]);*/
			}
		}
	/*for(i = 0;i <= ((n+1)*(m+1)-1); i++) printf("%d",strel[i]);
	printf("\n");
	for(i = 0;i <= ((n+1)*(m+1)-1); i++) printf("%d",mass[i]);
	printf("\n");*/
	PrintLSC(strel, f2, --i, --j, n, m, &l, &pr);
	free(mass);
	free(strel);
	return;
	}

void compare(char *name1, char *name2)
	{
	int m, n;
	char **f1, **f2;
	FILE *fp1, *fp2;

	fp1 = fopen(name1, "r");
	fp2 = fopen(name2, "r");
	m = count (fp1);
	fclose(fp1);
	fp1 = fopen(name1, "r");
	f1 = input(fp1, &m, f1);
	/*for(j = 1;j <= m; j++) fprintf(stderr, "%s2\n",f1[j * sizeof(char*)]);*/
	n = count (fp2);
	fclose(fp2);
	fp2 = fopen(name2, "r");
	f2 = input(fp2, &n, f2);
	/*for(j = 1;j <= n; j++) fprintf(stderr, "%s3\n",f2[j * sizeof(char*)]);*/
	LCSLength(f1, f2, n, m);
	clear(f1, m);
	clear(f2, n);
	fclose(fp1);
	fclose(fp2);

	return;
	}

int errorS(FILE *fp1, FILE *fp2, char **f2, int len)
	{
	int i=0, n, boo, j ,mi = 0, zv = 0, ch;
	char word[MAX + 2];

	fgets(word,MAX+1,fp1);
	while (((n = strlen(word)) >= 2) && !feof(fp1))
		{
		boo = 1;
		for (j = 0; j < n; j++) if (word[j] == '\n') boo = 0;
		/*printf("%d %s",boo, word);*/
		if (boo == 1) {fprintf(stderr, "diff.patch.while: script is incorrect\n");return (1);}
		switch (word[i++])
			{
			case '-' :
				{
				if ((n == 2) || (mi > 0)) {fprintf(stderr, "diff.patch.case 1-: script is incorrect\n");return (1);}
				else
					{
					ch = zv = 0;
					mi = 1;
					for (i=1; i<=n-2; i++) if (!isdigit((int)(word[i]))){fprintf(stderr, "diff.patch.case 2-: script is incorrect\n");return (1);}
					for (i= 1; i < n-1; i++) {ch *= 10; ch += (word[i] - '0');}
					len -= ch;
					if (len < 0) {fprintf(stderr, "diff.patch.case len-: script is incorrect\n");return (1);}
					}
				break;
				}
			case '+' :
				{
				if (n == 2) {fprintf(stderr, "diff.patch.case 1+: script is incorrect\n");return (1);}
				else
					{
					mi = zv = 0;
					for (i=1; i<=n-2; i++) if ((word[i] == '-') || (word[i] == '*') || (word[i] =='+')) {fprintf(stderr, "diff.patch.case 2+: script is incorrect\n");return (1);}
					}
				break;
				}
			case '*' :
				{
				if ((n == 2) || (zv > 0)) {fprintf(stderr, "diff.patch.case 1*: script is incorrect\n");return (1);}
				else
					{
					ch = mi = 0;
					zv = 1;
					for (i=1; i<=n-2; i++)
						 if (!isdigit((int)word[i])){fprintf(stderr, "diff.patch.case 2*: script is incorrect\n");return (1);}
					for (i= 1; i < n-1; i++) {ch *= 10; ch += (word[i] - '0');}
					len -= ch;
					if (len < 0) {fprintf(stderr, "diff.patch.case len*: script is incorrect\n");return (1);}
					}
				break;
				} 
			default : {fprintf(stderr, "diff.patch.default: script is incorrect\n");return (1);}
			}
		i = 0;
		fgets(word,MAX+1,fp1);
		}
	/*printf("%d",len);*/
	if (len == 0) return (0);
	else {fprintf(stderr, "diff.patch len: script is incorrect\n");return(1);}
	}

void printS(FILE *fp1, FILE *fp2, char **f2)
	{
	long ch, in = 1, i, n;
	char word[MAX];

	fgets(word,MAX+1,fp1);
	while (((n = strlen(word)) >= 2) && !feof(fp1))
		{
		/*printf("%s %d\n",word,n);*/
		switch (word[0])
			{
			case '-' :
				{
				ch = 0;
				for (i= 1; i < n - 1; i++) {ch *= 10; ch += (word[i] - '0');}
				in += ch;
				break;
				}
			case '+' :
				{
				for (i= 1; i < n - 1; i++) putchar(word[i]);
				putchar(' ');
				break;
				}
			case '*' :
				{
				ch = 0;
				for (i= 1; i < n-1; i++) {ch *= 10; ch += (word[i] - '0');}
				for(i = in;i < in + ch; i++)
					printf("%s ",f2[i*sizeof(char*)]);
				in += ch;
				break;
				}
			}
		fgets(word,MAX+1,fp1);
		}
	printf("\n");
	return;
	}

void patch(char *name1, char *name2)
	{
	int m;
	char **f2;
	FILE *fp1, *fp2;

	fp1 = fopen(name1, "r");
	fp2 = fopen(name2, "r");
	m = count (fp2);
	fclose(fp2);
	fp2 = fopen(name2, "r");
	f2 = input(fp2, &m, f2);
	if (errorS(fp1, fp2, f2, m) == 0) {fclose(fp1);fp1 = fopen(name1, "r"); printS(fp1, fp2, f2);}
	clear(f2, m);
	fclose(fp1);
	fclose(fp2);

	return;
	}

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

	if (argc == 4)
		{
		if (strcmp(argv[1], "--patch") == 0)  patch(argv[2], argv[3]);
		else if (strcmp(argv[1], "--compare") == 0)  compare(argv[2], argv[3]);
			else fprintf(stderr, "diff.main: error in mode\n");
		}
	else fprintf(stderr, "diff.main: error in number of arguments\n");

	return 0;
	}