Pagini recente » Cod sursa (job #2655732) | Cod sursa (job #166732) | Cod sursa (job #1052534) | Cod sursa (job #1574082) | Cod sursa (job #2069474)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
vector <string> adn;
vector <int> leg;
bool bun[20];
int lp[19][30];
int ma[20][20];
int n;
bool viz[20];
int v[20];
string text;
int best;
int bs[20];
int cn;
void perm(int p,int t ,long long c)
{
if(p==n)
{
if(best<c)
{
best=c;
for(int i=0;i<n;i++)
{
bs[i]=v[i];
}
}
return ;
}
for(int i=0;i<cn;++i)
{
if(!viz[i])
{
viz[i]=1;
v[p]=i;
perm(p+1,i,c+ma[t][i]);
viz[i]=0;
}
}
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d\n", &n);
int l;
for(int k=0; k<n; ++k)
{
getline(cin,text);
l=text.length();
leg.push_back(l);
adn.push_back(text);
int j=0;
for (int i=1; i<l; i++)
{
while (j>0 && text[i]!=text[j])
j=lp[k][j-1];
if(text[i]==text[j])
++j;
lp[k][i]=j;
}
}
for(int k=0; k<n; ++k)
{
if(!bun[k])
{
for(int q=0; q<n; ++q)
{
if(!bun[q] && k!=q)
{
int j=0;
for(int i=0;i<leg[k];++i)
{
while(j && adn[q][j]!=adn[k][i])
j=lp[q][j-1];
if(adn[q][j]==adn[k][i])
++j;
if(j==leg[q])
{
bun[k]=1;
ma[k][q]=0;
break;
}
}
ma[k][q]=j;
}
}
}
}
for(int i=0;i<n;i++)
if(!bun[i])
cn++, viz[i]=1;
swap(cn,n);
for(int i=0;i<cn;i++)
{
if(!bun[i])
viz[i]=1,v[0]=i, perm(1,i,0), viz[i]=0;
}
cout<<adn[bs[0]];
for(int i=1;i<n;i++)
{
cout<<adn[bs[i]].substr(ma[bs[i-1]][bs[i]]);
}
return 0;
}