Cod sursa(job #473932)

Utilizator blasterzMircea Dima blasterz Data 1 august 2010 18:29:08
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


int n;

char a[20][30003];
int len[20];

int dist[20][20];
int t[30003];

int calcDist (char a[], char p[], int n, int m)
{
	int i, k;
	memset (t, 0, sizeof (t));
	t[1] = 0;
	k = 0;

	for (i = 2; i <= m; ++i)
	{
		while (k && p[i] != p[k + 1])
			k = t[k];
		
		if (p[i] == p[k + 1])
			++k;
		t[i] = k;
	}
	
	k = 0;
	
	for (i = 1; i <= n; ++i)
	{
		while (k && a[i] != p[k + 1])
			k = t[k];
		
		if (a[i] == p[k + 1])
			++k;
		if (k == m)
			return m;
	}
	
	return k;
}

void brut ()
{
	int x[19];
	int sol[19];
	int mx = 0;
	int i;
	for (i = 1; i <= n; ++i)
		x[i] = i;
	
	
	int c = 0;
	
	do
	{
		c = 0;
		for (i = 2; i <= n; ++i)
			c += dist[x[i - 1]][x[i]];
		
		if (c >= mx)
		{
			mx = c;
			for (i = 1; i <= n; ++i)
				sol[i] = x[i];
		}
		
	}while (next_permutation (x + 1, x + n + 1));
	
	//for (i = 2; i <= n; ++i)
	//	printf ("%d\n", dist[sol[i - 1]][sol[i]]);

	printf ("%s", a[sol[1]] + 1);
	
	
	for (i = 2; i <= n; ++i)
	{
		if (dist[sol[i - 1]][sol[i]] != len[sol[i]])
			printf ("%s", a[sol[i]] + dist[sol[i - 1]][sol[i]]  + 1);
		
	}
	
	printf ("\n");
}


int main ()
{
	freopen ("adn.in", "r", stdin);
	freopen ("adn.out", "w", stdout);
	
	scanf ("%d\n", &n);
	
	int i, j;
	
	for (i = 1; i <= n; ++i)
	{
		scanf ("%s\n", &a[i]);
		
		len[i] = strlen (a[i]);
		
		for (j = len[i]; j > 0; --j)
			a[i][j] = a[i][j - 1];
		a[i][len[i] + 1] = 0;
	
	//	printf ("%s\n", a[i] + 1);
	}
	
	for (i = 1; i <= n; ++i)
		for (j = 1; j <= n; ++j)
			if (i != j)
				dist[i][j] = calcDist (a[i], a[j], len[i], len[j]);

	
	brut ();
	
	return 0;
}