Pagini recente » Cod sursa (job #2586617) | Cod sursa (job #1638311) | Cod sursa (job #2771357) | Cod sursa (job #2393605) | Cod sursa (job #2818370)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
#define Max 32000
int main()
{
int i,j,n,k,s,mx=0,p[20],pmax[20],D[20][20],L[20];
char cuv[20][Max],c[Max];
fin>>n;
for (i=0;i<n;i++)
{fin>>cuv[i]; L[i]=strlen(cuv[i]);}
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (L[i]<L[j])
{swap(cuv[i],cuv[j]); swap(L[i],L[j]);}
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (strstr(cuv[i],cuv[j])) L[j]=0;
for (i=0;i<n;i++)
if (L[i]==0)
{swap(L[i],L[n-1]); n--;}
for (i=0;i<n;i++) {
strcpy(c,cuv[i]);
for (j=0;j<n;j++) {
k=min(L[i],L[j]);
while (k>0 && strncmp(c+L[i]-k,cuv[j],k)!=0)k--;
D[i][j]=k;
}
}
for (i=0;i<n;i++) p[i]=i;
do {
s=0;
for (i=1;i<n;i++) s+=D[p[i-1]][p[i]];
if (s>mx)
{mx=s; for(j=0;j<n;j++) pmax[j]=p[j];}
} while (next_permutation(p,p+n));
fout<<cuv[pmax[0]];
for(i=1;i<n;i++) {strcpy(c,cuv[pmax[i]]);fout<<c+D[pmax[i-1]][pmax[i]];}
return 0;
}