Cod sursa(job #235846)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 26 decembrie 2008 00:07:51
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
using namespace std;

#include <bitset>
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN  "adn.in"
#define OUT "adn.out"
#define N_MAX 1<<5
#define L_MAX 1<<15
#define oo 1<<30
#define p(x) (1<<(x-1))

char V[N_MAX][L_MAX];
int P[N_MAX][N_MAX],L[N_MAX],A[1<<18][19];
int pi[L_MAX],N,K;

II void print(int x,int y);
II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d\n",&N);
	FOR(i,1,N)
	{
		scanf("%s",&V[i]);
		for(int j=0;V[i][j] != '\0';L[i] = j,++j);
	}	
	K = (1<<N)-1;
}

II void prefix(char N[],int n)
{
	int k = 0;
	pi[0] = 0;
	
	FOR(i,1,n)
	{
		while(k && N[k] != N[i])
			k = pi[k-1];
		if(N[k] == N[i])
			++k;
		pi[i] = k;
	}	
}

II int kmp(char N[],char M[],int n,int m)
{
	int q = 0;
	
	FOR(i,0,m)
	{
		while(q && N[q] != M[i])
			q = pi[q-1];
		if(N[q] == M[i])
			++q;
		if(q==n+1)
			return oo;
	}	
	return q;
}

II void solve()
{
	memset(A,100,sizeof(A));
	A[0][0] = 0;
	
	FOR(i,1,N)
	FOR(j,1,N)
	if(i!=j && (K & p(j) ) )
	{
		prefix(V[j],L[j]);
		P[i][j] = kmp(V[j],V[i],L[j],L[i]);
		if(P[i][j] == oo)
			K ^= p(j);
	}	
	
	FOR(i,1,K)
	FOR(j,1,N)
	{
		if(!p(j) & (i||K) )
			continue;
		FOR(k,0,N)
		{
			if(k==j)
				continue;
			A[i][j] = min(A[i][j],A[i ^ p(j)][k] - P[k][j]);
		}
	}	
	
	int poz(0);
	A[K][0] = oo;
	FOR(i,1,N)
		if(A[K][i] < A[K][poz])
			poz = i;
	print(K,poz);	
}

II void print(int x,int y)
{
	if(x == p(y))
	{
		printf("%s",V[y]);
		return;
	}	
	FOR(i,1,N)
		if(A[x ^ p(y)][i] - P[i][y] == A[x][y])
		{
			print(x ^ p(y),i);
			printf("%s",V[y]+P[i][y]);
			return;
		}	
}

int main()
{
	scan();
	solve();
	return 0;
}