Pagini recente » Cod sursa (job #1200575) | Cod sursa (job #493553) | Cod sursa (job #1654544) | Cod sursa (job #554092) | Cod sursa (job #562889)
Cod sursa(job #562889)
#include <cstdio>
#include <cstring>
int a[20][20],C[(1<<18)+9][20],bf[(1<<18)+9][20],n,x;
void rez(int secv,int poz)
{
if (C[secv][poz]!=-1) return ;
int i;
if (!secv) return ;
C[secv][poz]=1<<19;
for (i=1;i<=n;++i)
if (secv&(1<<i))
if ((i==x) && (secv!=1<<x)) continue; else
{
rez(secv^(1<<i),i);
if (C[secv^(1<<i)][i]+a[i][poz]<C[secv][poz])
C[secv][poz]=C[secv^(1<<i)][i]+a[i][poz],bf[secv][poz]=i;
}
}
int main()
{
int i,j,k,b,v[20],pi[30003],sol=3000000,ps[20];
char s[20][30003];
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{scanf("%s",s[i]);v[i]=strlen(s[i]);}
for (i=1;i<=n;++i)
{
k=0;pi[1]=0;
for (j=2;j<=v[i];++j)
{
for (;k&&(s[i][j-1]!=s[i][k]);)
k=pi[k];
if (s[i][j-1]==s[i][k]) k++;
pi[j]=k;
}
k=0;
for (b=1;b<=n;++b)
if (b!=i)
{
for (j=1;j<=v[b];j++)
{
for (;k&&(s[b][j-1]!=s[i][k]);) k=pi[k];
if (s[b][j-1]==s[i][k]) k++;
if (k==v[i]) break;
}
a[b][i]=v[i]-k;
}
}
for (x=1;x<=n;++x)
{
memset(C, -1, sizeof(C));
C[0][x]=0;b=-1;
for (j=1;j<=n;++j)
if (x!=j)
{
rez((((1<<(n+1))-1)^(1<<j))^1,j);
C[(((1<<(n+1))-1)^(1<<j))^1][j]+=v[x];
if (sol>C[(((1<<(n+1))-1)^(1<<j))^1][j])
{sol=C[(((1<<(n+1))-1)^(1<<j))^1][j];b=j;}
}
if (b>0)
{
pi[pi[0]=1]=b;j=(((1<<(n+1))-1)^(1<<b))^1;
while (b!=x)
pi[++pi[0]]=(b=bf[j][b]),j=j^(1<<b);
}
}
printf("%s",s[pi[pi[0]]]);
for (i=pi[0]-1;i;--i)
if (a[pi[i+1]][pi[i]]==0) pi[i]=pi[i+1]; else
printf("%s",s[pi[i]]+v[pi[i]]-a[pi[i+1]][pi[i]]);
printf("\n");
return 0;
}