Cod sursa(job #473943)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 1 august 2010 20:13:28
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<algorithm>
#include<string.h>
using namespace std;

#define N_MAX 18
#define L_MAX 30005
#define MAX 1<<29

int Kmp[L_MAX];
char c[N_MAX][L_MAX];

int i,j,n,k;
int cost[N_MAX][N_MAX];

#define CONFIG 1<<N_MAX
int dp[CONFIG][N_MAX];
int t[CONFIG][N_MAX];
void Prefix(char *c)
{
	memset(Kmp,0,sizeof(Kmp));

	int sz=strlen(c)-2,i;
	int k=0;

	for(i=2;i<=sz;i++)
	{
		while(k>0&&c[k+1]!=c[i])
			k=Kmp[k];

		if(c[k+1]==c[i])
			++k;
		
		Kmp[i]=k;
	}
}

int Cmp(char *x,char *y)
{
	int szx=strlen(x)-2,szy=strlen(y)-2;

	Prefix(y);
	int k=0,i;
	for(i=1;i<=szx;i++)
	{
		while(k>0&&y[k+1]!=x[i])
			k=Kmp[k];

		if(y[k+1]==x[i])
			++k;

		if(k==szy)
		{
			return i-szx;
		}
	}

	return szy-k;
}
int OK=1;
void REC(int config,int i)
{
	if(i==-1)
		return;
	REC(config-(1<<i),t[config][i]);
	if(cost[t[config][i]][i]==-1)
		return ;
	else
	{
		int sz=strlen(c[i])-2;
		if(OK)
		{
			for(int j=0;j<=sz;j++)
				printf("%c",c[i][j]);
			OK=0;
		}
		else
		{
			for(int j=sz-cost[t[config][i]][i]+1;j<=sz;j++)
				printf("%c",c[i][j]);
		}
	}
}

int main()
{
	freopen("adn.in","r",stdin);
	freopen("adn.out","w",stdout);

	scanf("%d\n",&n);

	for(i=0;i<n;i++)
	{
		c[i][0]=' ';
		fgets(c[i]+1,L_MAX,stdin);
	}

	for(i=0;i<CONFIG;i++)
		for(j=0;j<n;j++)
			dp[i][j]=MAX;

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j)
				cost[i][j]=(1<<30);
			else
				cost[i][j]=Cmp(c[i],c[j]);

			dp[(1<<j)][j]=0;
			t[(1<<j)][j]=-1;
		}
	}

	for(i=0;i<(1<<n);i++)
	{
		for(j=0;j<n;j++)
		{
			if((i&(1<<j))==0)
				continue;
			for(k=0;k<n;k++)
			{
				if((i&(1<<k))==0||k==j)
					continue;
				if(dp[i][j]>dp[i-(1<<j)][k]+cost[k][j])
				{
					dp[i][j]=dp[i-(1<<j)][k]+cost[k][j];
					t[i][j]=k;
				}
			}
		}
	}
	int Min=0,ind=0;
	for(i=1;i<n;i++)
		if(Min>dp[(1<<n)-1][i])
			Min=dp[(1<<n)-1][i],ind=i;

	REC((1<<n)-1,ind);

	return 0;
}