Cod sursa(job #139729)

Utilizator flionIonescu Ionut Florin flion Data 20 februarie 2008 16:18:34
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.55 kb
// DEBUG VERSION, good for visual backtracking

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

#define nmax 25
#define lmax 25

void start();
void got(int, int);
void gos(int, int);

int N, M, ok, Length_;
int Lengths[nmax], Lengtht[nmax];
char S[nmax][lmax], T[nmax][nmax];
int usedt[nmax], useds[nmax];
int length_solutiont, length_solutions;
char string_solutiont[lmax], string_solutions[lmax];
int OK[nmax][nmax], DONE;
int sufs[nmax][nmax][lmax], suft[nmax][nmax][lmax];

int match(int i, int j)
{
	int s;

	for (s = 1; s <= Lengths[i] && s <= Lengtht[j]; s++)
		if (S[i][s] != T[j][s])
			return 0;
	return OK[i][j] = s-1;
}

int suffs(int top, int number, int j)
{
	if (sufs[top][j][number])
		return sufs[top][j][number];

	int i;
	for (i = 1; i <= Lengtht[j] && i <= number; i++)
		if (S[top][Lengths[top]-number+i] != T[j][i])
			return sufs[top][j][number] = 2;

	if (i > 1)
		return sufs[top][j][number] = 1;
	return sufs[top][j][number] = 2;
}

int sufft(int top, int number, int i)
{
	if (suft[top][i][number])
		return suft[top][i][number];

	int j;
	for (j = 1; j <= Lengths[i] && j <= number; j++)
		if (T[top][Lengtht[top]-number+j] != S[i][j])
			return suft[top][i][number] = 2;

	if (j > 1)
		return suft[top][i][number] = 1;

	return suft[top][i][number] = 2;
}

void read()
{
	int i;

	freopen("findit.in", "r", stdin);
	scanf("%d %d\n", &N, &M);

	for (i = 1; i <= N; S[i++][0] = ' ')
		scanf("%s\n", &S[i][1]);

	for (i = 1; i <= M; T[i++][0] = ' ')
		scanf("%s\n", &T[i][1]);
}

void write()
{
	freopen("findit.out", "w", stdout);
	printf("%s\n", string_solutions+1);
}

void gos(int number, int top)
{
	int j, x, i, k, oks;

	for (j = 1; j <= M && !DONE; ++j)
		if (!usedt[j])
		{
			oks = suffs(top, number, j);

			if (oks == 1)
			{
				usedt[j] = 1;

				for (k = 1; k <= Lengtht[j]; k++)
					string_solutiont[k + length_solutiont] = T[j][k];

				length_solutiont += Lengtht[j];

				string_solutiont[length_solutiont + 1] = NULL;

				if (length_solutions > length_solutiont)
					gos(length_solutions - length_solutiont, top);
				else if (length_solutions < length_solutiont)
					got(length_solutiont - length_solutions, j);
				else
					start();

				length_solutiont -= Lengtht[j];

				string_solutiont[length_solutiont + 1] = NULL;

				usedt[j] = 0;
			}
		}
}

void got(int number, int top)
{
	int i, x, j, k, okt;

	for (i = 1; i <= N && !DONE; ++i)
		if (!useds[i])
		{
			okt = sufft(top, number, i);

			if (okt == 1)
			{
				useds[i] = 1;

				for (k = 1; k <= Lengths[i]; k++)
					string_solutions[k + length_solutions] = S[i][k];

				length_solutions += Lengths[i];

				string_solutions[length_solutions + 1] = NULL;

				if (length_solutions > length_solutiont)
					gos(length_solutions - length_solutiont, i);
				else if (length_solutions < length_solutiont)
					got(length_solutiont - length_solutions, top);
				else
					start();

				length_solutions -= Lengths[i];

				string_solutions[length_solutions + 1] = NULL;

				useds[i] = 0;
			}
		}
}

void start()
{
	if (length_solutions == Length_ && length_solutiont == Length_)
	{
		DONE = 1;

		write();
	}

	int i, j, k;
	for (i = 1; i <= N && !DONE; ++i)
		if (!useds[i])
			for (j = 1; j <= M && !DONE; ++j)
				if (!usedt[j] && OK[i][j])
				{
					useds[i] = usedt[j] = 1;

					for (k = 1; k <= Lengths[i]; ++k)
						string_solutions[k+length_solutions] = S[i][k];

					for (k = 1; k <= Lengtht[j]; ++k)
						string_solutiont[k+length_solutiont] = T[j][k];

					length_solutions += Lengths[i];
					length_solutiont += Lengtht[j];

					string_solutions[length_solutions + 1] = NULL;
					string_solutiont[length_solutiont + 1] = NULL;

					if (length_solutions > length_solutiont)
						gos(length_solutions - length_solutiont, i);
					else if (length_solutions < length_solutiont)
						got(length_solutiont - length_solutions, j);
					else
						start();

					length_solutions -= Lengths[i];
					length_solutiont -= Lengtht[j];

					string_solutions[length_solutions + 1] = NULL;
					string_solutiont[length_solutiont + 1] = NULL;

					useds[i] = usedt[j] = 0;
				}
}

void solve()
{
	int i, j;

	string_solutions[0] = string_solutiont[0] = ' ';

	for (i = 1; i <= N; ++i)
		Length_ += Lengths[i] = strlen(S[i])-1;

	for (i = 1; i <= M; ++i)
		Lengtht[i] = strlen(T[i])-1;

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			OK[i][j] = match(i, j);

	start();
}

void main()
{
	read();

	solve();
}