Pagini recente » Cod sursa (job #2188754) | Cod sursa (job #2631392) | Cod sursa (job #1696927) | Cod sursa (job #1236643) | Cod sursa (job #473943)
Cod sursa(job #473943)
#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;
}