Pagini recente » Cod sursa (job #240779) | Cod sursa (job #262952) | Cod sursa (job #2566045) | Cod sursa (job #2719247) | Cod sursa (job #562767)
Cod sursa(job #562767)
#include <cstdio>
#include <cstring>
int a[20][20],lung,now,x[20],p[20],C[(1<<18)+1][20],n;
void rez(int secv,int poz)
{
if (C[secv][poz]!=-1) return ;
int i;
if (!secv)
{if (lung<now) {now=lung;for (i=0;i<=p[0];++i) x[i]=p[i];}
return ;
}
C[secv][poz]=90000000;
for (i=1;i<=n;++i)
if (secv&(1<<i))
{
if (a[p[p[0]]][i]==0) rez(secv^1<<i,poz); else
lung+=a[p[p[0]]][i],p[++p[0]]=i,rez(secv^1<<i,i),--p[0],lung-=a[p[p[0]]][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 (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (i!=j)
{
lung=v[i]+a[i][j];
memset(C, -1, sizeof(C));
x[0]=p[0]=2;x[1]=p[1]=i;x[2]=p[2]=j;now=sol;
rez(((((1<<(n+1))-1)^(1<<i))^(1<<j))^1,j);
if (sol>now)
{sol=now;for (b=0;b<=x[0];++b) ps[b]=x[b];}
}
printf("%s",s[ps[1]]);
for (i=2;i<=ps[0];++i)
printf("%s",s[ps[i]]+v[ps[i]]-a[ps[i-1]][ps[i]]);
printf("\n");
return 0;
}