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

char* nLCS(const char* x, const char* y, size_t n, size_t m, size_t* len)
{
	if (n < 1 || m < 1) {
		*len = 0;
		return (char*) calloc(1, sizeof(char));
	} else
	if (x[n - 1] == y[m - 1]) {
		size_t L;
		char* s = nLCS(x, y, n - 1, m - 1, &L);
		s = (char*) realloc(s, sizeof(char) * L + 2);
		s[L] = x[n - 1];
		s[L + 1] = 0;
		*len = L + 1;
		return s;
	} else {
		size_t Lx, Ly;
		char* sx = nLCS(x, y, n - 1, m, &Lx);
		char* sy = nLCS(x, y, n, m - 1, &Ly);
		short B = Lx > Ly;
		free(B ? sy : sx);
		*len = B ? Lx : Ly;
		return B ? sx : sy;
	}
}

char* LCS(const char* x, const char* y)
{
	size_t len;
	return nLCS(x, y, strlen(x), strlen(y), &len);
}

typedef struct {
	size_t len;
	short dec_x;
} table_rec;

void LCS_fill_table(const char* x, const char* y, size_t n, size_t m, 
					table_rec** t)
{
	for (size_t i = 1; i <= n; i++) {
		for (size_t j = 1; j <= m; j++) {
			if (x[i - 1] == y[j - 1]) {
				t[i][j].len = t[i - 1][j - 1].len + 1;
				t[i][j].dec_x = 1;
			} else {
				size_t LX = t[i - 1][j].len;
				size_t LY = t[i][j - 1].len;
				t[i][j].len = (LX > LY) ? LX : LY;
				t[i][j].dec_x = LX > LY;
			}
		}
	}
}

void nDynamicLCS(const char* x, const char* y, size_t n, size_t m, 
				 table_rec** t, char* out)
{
	size_t len = t[n][m].len;
	if (len < 1) return;
	if (x[n - 1] == y[m - 1]) {
		out[len - 1] = x[n - 1];
		nDynamicLCS(x, y, n - 1, m - 1, t, out);
	} else {
		short dec_x = t[n][m].dec_x;
		out[len - 1] = dec_x ? x[n - 1] : y[n - 1];
		if (dec_x)
			nDynamicLCS(x, y, n - 1, m, t, out);
		else
			nDynamicLCS(x, y, n, m - 1, t, out);
	}
}

char* DynamicLCS(const char* x, const char* y)
{
	size_t n = strlen(x), m = strlen(y);
	table_rec** t = (table_rec**) malloc(sizeof(table_rec*) * (n + 1));
	size_t i;
	for (i = 0; i <= n; i++)
		t[i] = (table_rec*) calloc(m + 1, sizeof(table_rec));
	LCS_fill_table(x, y, n, m, t);
	char* r = (char*) calloc((1 + t[n][m].len), sizeof(char));
	nDynamicLCS(x, y, n, m, t, r);
	for (i = 0; i < n; i++) free(t[i]);
	free(t);
	return r;
}

char* zargari(const char* s)
{
	size_t len = strlen(s);
	char* r = (char*) calloc(2 * (len + 1), sizeof(char));
	const char* t = s;
	size_t i = 0, c = 0;
	while (t[i]) {
		if (t[i + 1] != ' ' && t[i + 1])
			r[c++] = t[++i];
		else {
			r[c++] = t[0]; r[c++] = 'a';
			r[c++] = 'y'; r[c++] = t[i + 1];
			t += i + 1 + (t[i + 1] ? 1 : 0);
			i = 0;
		}
	}
	return (char*) realloc(r, sizeof(char) * (strlen(r) + 1));
}

int main(int argc, char* argv[])
{
	return 0;
}