Pagini recente » Cod sursa (job #16229) | Cod sursa (job #380180) | Cod sursa (job #34344) | Cod sursa (job #32792) | Cod sursa (job #40352)
Cod sursa(job #40352)
#include<fstream.h>
#include<string.h>
#include<stdlib.h>
#define nmax 30004
#define tmax 100000
int n,m[19][19],adev[nmax];
char s[19][nmax];
long lung,d,viz[19],i,j,k,n1,n2;
void rezolva();
void afiseaza(int d[100]);
int main()
{ifstream f("adn.in");
f>>n;
for(i=1;i<=n;i++)
f>>s[i];
// daca unul contine pe celalalt
memset(viz,0,sizeof(viz));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j&&strstr(s[i],s[j]))
viz[j]=1;
for(i=1,d=0;i<=n;i++)
if(!viz[i])
{memcpy(s[++d],s[i],sizeof(s[i]));
lung+=strlen(s[i]);
}
n=d;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(j!=i)
{memset(adev,1,sizeof(adev));
for(k=0,n1=strlen(s[i]),n2=strlen(s[j]);k<n1;k++)
for(d=0;d<k;d++)
if(s[j][d]!=s[i][n1-(k-d)])
{adev[k]=0;break;}
for(k=n1-1;k>=0;k--)
if(adev[k])
{m[i][j]=k;break;}
}
rezolva();
return 0;
}
void rezolva()
{//randomize();
int j,x,viz[19],s[19],d[19];
long l,i,min=1000000;
for(k=1;k<=tmax;k++)
{memset(viz,0,sizeof(viz));
for(j=1;j<=n;j++)
{
//do{
x=rand()%n+1;
// }
while(viz[x]&&x) x--;
if(!x) {x=n; while(!viz[x]) x--;}
viz[x]=1;
s[j]=x;
}
for(j=1,l=lung;j<n;j++)
l-=m[s[j]][s[j+1]];
if(l<min)
{min=l;memcpy(d,s,sizeof(s));}
}
afiseaza(d);
}
void afiseaza(int d[100])
{int i,j;
ofstream g("adn.out");
for(i=1;i<n;i++)
for(j=0;j<=strlen(s[d[i]])-m[d[i]][d[i+1]]-1;j++)
g<<s[d[i]][j];
g<<s[d[i]];
g.close();
}