Pagini recente » Cod sursa (job #576215) | Cod sursa (job #2120537) | Cod sursa (job #1958694) | Cod sursa (job #2287534) | Cod sursa (job #327536)
Cod sursa(job #327536)
#include<fstream>
#include<string.h>
#include<stdio.h>
using namespace std;
int cost[20][20],sol[20],viz[20],v[20],max1=-1,n,i,min1=50000;
char a[20][30010];
void citire(){
int i;
ifstream f("adn.in");
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
}
void eliminare(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(strstr(a[j],a[i])&&i!=j){
{
strcpy(a[i],a[n]);
n--;
}
}
}
int calc_cost(char *a,char *b){
int n=strlen(a);
int i,k=0;
for(i=0;i<n;i++)
if(a[i]==b[k])k++;
else
k=0;
return k;
}
void afisare(int v[]){
int i,m,j;
freopen("adn.out","w",stdout);
for(i=1;i<n;i++)
{m=strlen(a[v[i]]);
for(j=1;j<=m-cost[v[i]][v[i+1]];j++)
printf("%c",a[v[i]][j-1]);
}
printf("%s",a[v[n]]);
}
void cost1(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
cost[i][j]=calc_cost(a[i],a[j]);
}
void cond(){
int i,sum=0;
for(i=1;i<n;i++)
sum+=cost[v[i]][v[i+1]];
if(sum>max1){max1=sum;memcpy(sol,v,sizeof(v));}
}
void back(int lvl){
if(lvl==n)cond();
else
{int i;
for(i=1;i<=n;i++)
if(!viz[i])
{viz[i]=1;
v[lvl+1]=i;
back(lvl+1);
viz[i]=0;}
}
}
int main(){
citire();
eliminare();
cost1();
back(0);
afisare(sol);
return 0;}