Pagini recente » Cod sursa (job #994880) | Cod sursa (job #910464) | Cod sursa (job #288864) | Autentificare | Cod sursa (job #1403364)
#include <cstdio>
#include <cstring>
using namespace std;
const int maxlen=30001;
char v[20][maxlen],vaz[20];
int cost[20][20],v1[20],din[270000][19],tata[270000][19],sol[20],n,i,j,q,minn,nrsol,lim,nr;
int kmp(char v[maxlen],char v1[maxlen])
{
int pi[maxlen],k=-1,i,n=strlen(v),m=strlen(v1);
pi[0]=-1;
for(i=1;i<n;i++)
{
while(k>-1 && v[k+1]!=v[i]) k=pi[k];
if(v[k+1]==v[i]) k++;
pi[i]=k;
}
k=-1;
for(i=0;i<m;i++)
{
while(k>-1 && v[k+1]!=v1[i]) k=pi[k];
if(v[k+1]==v1[i]) k++;
if(k==n-1) return 0;
}
return n-1-k;
}
int main()
{
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d\n",&n);
for(i=0;i<n;i++) scanf("%s\n",v[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
{
cost[i][j]=kmp(v[j],v[i]);
if(cost[i][j]==0) vaz[j]=1;
}
memset(din, 1000000, sizeof(din));
for(i=0;i<n;i++)
if(!vaz[i])
{
v1[nr]=i;
din[1<<nr][nr]=strlen(v[i]);
nr++;
}
lim=(1<<nr);
for(i=1;i<lim;i++)
for(j=0;j<nr;j++)
if(i&(1<<j))
{
for(q=0;q<nr;q++)
if(!(i&(1<<q)))
if(din[i|(1<<q)][q]>din[i][j]+cost[v1[j]][v1[q]])
{
din[i|(1<<q)][q]=din[i][j]+cost[v1[j]][v1[q]];
tata[i|(1<<q)][q]=j;
}
}
minn=1000000;
lim--;
for(i=0;i<nr;i++)
if(din[lim][i]<minn)
{
minn=din[lim][i];
j=i;
}
i=j;
while(lim>0)
{
sol[++nrsol]=v1[i];
j=tata[lim][i];
lim^=(1<<i);
i=j;
}
lim=strlen(v[sol[nrsol]]);
for(i=0;i<lim;i++) printf("%c",v[sol[nrsol]][i]);
for(i=nrsol-1;i;i--)
{
lim=strlen(v[sol[i]]);
for(j=lim-cost[sol[i+1]][sol[i]];j<lim;j++) printf("%c",v[sol[i]][j]);
}
return 0;
}