Cod sursa(job #576577)

Utilizator ilincaSorescu Ilinca ilinca Data 9 aprilie 2011 13:01:06
Problema ADN Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <cstdio>	
#include <cstring>

#define nmax 25
#define lmax 30015
#define nrstari (1<<18)+15

int n, toate, lungime [nmax], pi [nmax] [lmax], potrivire [nmax] [nmax], r [nmax] [nrstari];
bool ok [nmax];
char a [nmax] [lmax];
int prev [nmax] [nrstari];

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=0; i < n; ++i)
		scanf ("%s", a [i]+1);
}

void calc_pi (int k)
{
	int i, q=0;
	pi [k] [1]=0;
	for (i=2; a [k] [i]; ++i)
	{
		//fprintf (stderr, "!%c %c\n", a [k] [i], a [k] [q+1]);
		while (q && a [k] [i] != a [k] [q+1])
			q=pi [k] [q];
		if (a [k] [i] == a [k] [q+1]) ++q;
		pi [k] [i]=q;
	}
	lungime [k]=i-1;
	//fprintf (stderr, "!%d\n", i);
}

int kmp (int B, int A)
{
	int i, q=-1;
	for (i=1; a [B] [i]; ++i)
	{
		while (q && a [A] [q+1] != a [B] [i])
			q=pi [A] [q];
		if (a [A] [q+1] == a [B] [i]) ++q;
		if (q == lungime [A])
			return -1;
	}
	return q;
}

void calc_potrivire ()
{
	int i, j;
	for (i=0; i < n; ++i)
		calc_pi (i);
	//fprintf (stderr, "%s\n", a [0]);
	//for (i=1; a [0] [i]; ++i) fprintf (stderr, "%d ", pi [0] [i]);
	for (i=0; i < n; ++i)
		for (j=0; j < n; ++j)
		{
			if (i == j) continue;
			//potrivire [i] [j] = sufixul lui i care coincide cu prefixul lui j
			potrivire [i] [j]=kmp (i, j);
			if (potrivire [i] [j] == -1)
				ok [j]=true;		
			//fprintf (stderr, "%d %d %d\n", i, j, potrivire [i] [j]);
		}
	for (i=0; i < n; ++i)
		for (j=0; j < i; ++j)
			if (potrivire [i] [j] == -1 && potrivire [i] [j] == potrivire [j] [i])
				ok [j]=false;
}

int rez ()
{
	int i, j, k, stari=1<<n;
	for (i=0; i < stari; ++i)
		for (j=0; j < n; ++j)
			if (i & (1<<j))
			{
				if (ok [j])
					continue;
				for (k=0; k < n; ++k)
					if ((k != j) && (i & (1 << k)))
					{
						//fprintf (stderr, "%d %d %d %d %d %d\n", i, j, k, i^(1<<j), potrivire [k] [j], r [i^(1<<j)] [k]);
						if (r [j] [i] < r [k] [i^(1<<j)] + potrivire [k] [j])
						{
							r [j] [i]=r [k] [i^(1<<j)] + potrivire [k] [j];
							prev [j] [i]=k;
						}
						//fprintf (stderr, "!");
					}
			}
	int m=0, l=0;
	toate=(1<<n)-1;
	for (i=0; i < n; ++i)
		if (ok [i])
			toate ^= 1<<i;
	for (i=0; i < n; ++i)
		if (m < r [i] [toate])
		{
			m=r [i] [toate];
			l=i;
		}
//	for (i=0; i < n; ++i) 
//		if (ok [i] == true) fprintf (stderr, "!!!!!!!!!!%d\n", i);
/*	for (i=0; i < stari; ++i)
	{
		for (j=0; j < n; ++j)
			fprintf (stderr, "%d %d %d %d\n", i, j, r [j] [i], prev [j] [i]);
		fprintf (stderr, "\n");
	}*/
	return l;
}

void print (int stare, int l)
{	
//	fprintf (stderr, "!!");
//	fprintf (stderr, "%d %d %d %d\n", stare, l, prev [l] [stare], potrivire [l] [prev [l] [stare]]);
	if (stare == 0) return;
	if (r [l] [stare] == 0)
	{
		int i;
		for (i=0; i < n; ++i)
			if (stare & (1 << i))
				printf ("%s", a [i]+1);
		return;
	}
	print (stare^(1<<l), prev [l] [stare]);	
	printf ("%s", a [l]+1+potrivire [prev [l] [stare]] [l]);
}

int main ()
{
	freopen ("adn.in", "r", stdin);
	freopen ("adn.out", "w", stdout);
	scan ();
	calc_potrivire ();
	int l=rez ();
	//fprintf (stderr, "%d %d\n", toate, l);
	print (toate, l);
	return 0;
}