Pagini recente » Cod sursa (job #1614926) | Cod sursa (job #1014607)
#include<stdio.h>
#include<string.h>
int n,l[20],pi[20][30002],c[20],f[20][20],ds[30002][20],fct[300002][20];
char v[20][30002];
void funct()
{
int i,j,ls;
for(i=1;i<=n;++i)
{
ls=0;
for(j=2;j<=l[i];++j)
{
while(ls && v[i][ls+1]!=v[i][j])
ls=pi[i][ls];
if(v[i][ls+1]==v[i][j])
++ls;
pi[i][j]=ls;
}
}
}
int kmp(int x,int y)
{
int i,ls=0;
for(i=1;i<=l[x];++i)
{
while(ls && v[y][ls+1]!=v[x][i])
ls=pi[y][ls];
if(v[y][ls+1]==v[x][i])
++ls;
if(ls==l[y])
return ls;
}
return ls;
}
void afis(int x,int y)
{
if(x==(1<<y))
{
printf("%s",v[y]+1);
return;
}
afis(x^(1<<y),fct[x][y]);
printf("%s",(v[y]+1+f[fct[x][y]][y]));
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
int i,j,li,lj,ls,sol=0,max,aux;
scanf("%d\n",&n);
for(i=1;i<=n;++i)
{
gets(v[i]+1);
l[i]=strlen(v[i]+1);
}
funct();
for(i=1;i<=n;++i)
{
for(j=i+1;j<=n;++j)
{
li=kmp(i,j);
f[i][j]=li;
lj=kmp(j,i);
f[j][i]=lj;
if(li==l[j])
c[j]=1;
else if(lj==l[i])
c[i]=1;
}
}
memset(ds,2000000000,sizeof(ds));
for(i=1;i<=n;++i)
if(!c[i])
{
sol+=(1<<i);
ds[1<<i][i]=0;
}
max=(1<<n);
for(ls=1;ls<max;++ls)
{
for(i=1;i<=n;++i)
{
if(!c[i] && (ls&(1<<i)))
for(j=1;j<=n;++j)
if(!c[j] && !(ls&1<<j))
{
if(ds[ls^(1<<j)][j]>ds[ls][i]-f[i][j])
{
ds[ls^(1<<j)][j]=ds[ls][i]-f[i][j];
fct[ls^(1<<j)][j]=i;
}
}
}
}
ls=0;
for(i=2;i<=n;++i)
if(ds[sol][i]<ds[sol][ls])
ls=i;
afis(sol,ls);
printf("\n");
return 0;
}