Pagini recente » Cod sursa (job #2085982) | Cod sursa (job #1926817) | Cod sursa (job #2596508) | Cod sursa (job #2323467) | Cod sursa (job #197297)
Cod sursa(job #197297)
#include<stdio.h>
#include<string.h>
char s[20][30005];
long c[20][20],lung[20],prev[1<<18][20],cc[1<<18][20],inclus[20],N,M,
i,j,k,I8=1<<30,pi[20][30005];
void citire();
void prefix();
int KMP();
void pr_dinamica();
void print_sol();
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
citire();
for(int i=0; i<N; i++)prefix();
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{ if(i==j)
c[i][j]=0;
else
c[i][j]=KMP();
if(c[i][j]==-1)
inclus[j]=1;
}
pr_dinamica();
print_sol();
return 0;
}
void citire()
{
scanf("%ld",&N);M=1<<N;I8=1<<30;
for(int i=0; i<N; i++)
{
scanf("%s",s[i]+1);
lung[i]=strlen(s[i]+1);
}
}
void prefix()
{
int k=0,lsir=lung[i];
pi[i][1]=0;
for(int q=2; q<=lsir; ++q)
{
while(k>0 && s[i][q]!=s[i][k+1])
k=pi[i][k];
if(s[i][q]==s[i][k+1])
k++;
pi[i][q]=k;
}
}
int KMP()
{
int k=0,l1=lung[i],l2=lung[j],q;
for(q=1; q<=l1; q++)
{
while(k>0 && s[i][q]!=s[j][k+1])
k=pi[j][k];
if(s[i][q]==s[j][k+1])
k++;
if(k==l2)
return -1;
}
return k;
}
void pr_dinamica()
{
M=1<<N;I8=1<<30;
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{ if(!(i&(1<<j)))
cc[i][j]=I8;
else
if(i==(1<<j))
cc[i][j]=lung[j];
else
{
cc[i][j]=I8;
for(k=0;k<N;k++)
if(cc[i^(1<<j)][k]!=I8 && cc[i][j]>cc[i^(1<<j)][k]+lung[j]-c[k][j])
{
cc[i][j]=cc[i^(1<<j)][k]+lung[j]-c[k][j];
prev[i][j]=k;
}
}
}
}
void print_sol()
{ long h[20],t,cuv=0,pu,u=0,cs=0,min=I8;
for(i=0;i<N;i++)
if(!inclus[i])cs|=(1<<i);
for(i=0; i<N; i++)
if(!inclus[i] && min>cc[cs][i])
{
min=cc[cs][i];
u=i;
}
while(cs)
{ h[++cuv]=u;
pu=prev[cs][u];
cs^=u;
u=pu;
}
for(;cuv>1;cuv--)
{ t=lung[cuv]-c[h[cuv-1]][h[cuv]];
for(i=0;i<=t;i++)printf("%c",s[cuv][i]);
}
printf("%s",s[h[1]]);
}