Pagini recente » Cod sursa (job #2755309) | Cod sursa (job #1985243) | Cod sursa (job #3234982) | Cod sursa (job #3264185) | Cod sursa (job #2333669)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
int n,nr,i,j,a,b,l,m,k,ok,id;
int c[20][20],pi[30006],rz[262300][18],z[20];
char ch[524300][18];
string s[20],t[20],A,B;
void make_pi()
{
int k=0;
pi[1]=0;
for(int i=2;i<=a;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
int match()
{
int k=0;
for(int i=1;i<=b;i++)
{
while(k>0 && A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==a) ok=1;
}
return k;
}
int main() {
fin>>n;
for(i=1;i<=n;i++)
fin>>t[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j && t[i]!="" && t[j]!="")
{
A=" "+t[i];
B=" "+t[j];
a=(int)A.size()-1;
b=(int)B.size()-1;
ok=0;
make_pi();
nr=match();
if(ok) t[i]="";
}
m=n, n=0;
for(i=1;i<=m;i++)
if(t[i]!="") s[++n]=t[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
A=" "+s[j];
B=" "+s[i];
a=(int)A.size()-1;
b=(int)B.size()-1;
make_pi();
c[i][j]=match();
}
for(i=1;i<=n;i++)
rz[1<<(i-1)][i]=(int)s[i].size(), ch[1<<(i-1)][i]='0'+i;
m=(1<<n)-1;
for(l=1;l<m;l++)
for(i=1;i<=n;i++)
if(l&(1<<(i-1)))
for(j=1;j<=n;j++)
if(!(l&(1<<(j-1))))
{
k=l+(1<<(j-1));
nr=rz[l][i]-c[i][j]+(int)s[j].size();
if(rz[k][j]==0) rz[k][j]=660005;
if(nr<rz[k][j])
{
rz[k][j]=nr;
ch[k][j]='0'+i;
}
}
int rez=660005;
for(i=1;i<=n;i++)
if(rz[m][i]<rez)
rez=rz[m][i], id=i;
l=m, m=n;
while(id>0)
{
z[m--]=id;
k=(1<<(id-1));
id=ch[l][id]-'0';
l-=k;
}
for(i=1;i<n;i++)
{
l=(int)s[z[i]].size()-c[z[i]][z[i+1]];
for(j=1;j<=l;j++)
fout<<s[z[i]][j-1];
}
fout<<s[z[n]]<<"\n";
}