Pagini recente » Cod sursa (job #1996021) | Cod sursa (job #3281700) | Cod sursa (job #2930149) | Cod sursa (job #2207594) | Cod sursa (job #115)
Cod sursa(job #115)
#include <stdio.h>
#include <string.h>
#define nmax 20
#define lmax 30005
#define infinite 1000000
#define confmax 270000
long comps=0,comps1=0,n,cost,mmax,care,cost_max,cmax,cate[nmax],d[nmax][nmax],bagat[nmax],p[lmax],rez[nmax],aux[nmax],place[nmax][nmax],powe[nmax+1];
long cc[nmax][confmax],pd[nmax][confmax];
long prev[nmax][confmax];
char a[nmax][lmax];
void citire() {
scanf("%d\n",&n);
char ch;
for(long i=1;i<=n;i++) {
cate[i]=1;
scanf("%s\n",&a[i]);
cate[i]=strlen(a[i]);
for(long j=cate[i]+1;j>=1;j--) a[i][j]=a[i][j-1];
}
}
void kmp_calculeaza(long x) {
long n=cate[x];
long k=0;
p[1]=0;
for(int i=2;i<=n;i++) {
while ((k>0) && (a[x][k+1]!=a[x][i])) k=p[k];
if(a[x][k+1]==a[x][i]) k++;
p[i]=k;
}
}
long kmp_potrivire(long x,long y) {
int q=0;
int m=cate[y];
int n=cate[x];
for(long i=1;i<=m;i++) {
while((q>0) && (a[x][q+1]!=a[y][i])) q=p[q];
if(a[x][q+1]==a[y][i]) {
q++;
if(q==n) return q;
}
}
if(q==n) return 0;
return q;
}
long kmp(long x,long y) {
kmp_calculeaza(x);
return kmp_potrivire(x,y);
}
int nr1(long x) {
int cate=0;
while(x!=0) {
cate+=x %2;
x/=2;
}
return cate;
}
int main() {
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
citire();
long i,j;
for(i=1;i<=n;i++) bagat[i]=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if ((i!=j) && (bagat[i]) && (bagat[j])) {
long x=kmp(i,j);
if(x==cate[i]) bagat[i]=0;
d[j][i]=x;
}
powe[0]=1;
for(i=1;i<=nmax;i++) powe[i]=powe[i-1]*2;
long conf;
for(conf=1;conf<powe[n];conf++) {
long nr_1=nr1(conf);
cc[nr_1][++cc[nr_1][0]]=conf;
}
memset(pd,-1,sizeof(pd));
for(i=1;i<=n;i++) pd[i][powe[i-1]]=0;
long k;
long maxi=0,maxx,maxy;
int max1=0;
for(k=1;k<n;k++)
for(j=1;j<=cc[k][0];j++) {
long copy=cc[k][j];
for(int x1=1;x1<=n;x1++) {
if(copy%2==1) {
if ((pd[x1][cc[k][j]]!=-1) && (bagat[x1])) {
long copy1=cc[k][j];
for(int x2=1;x2<=n;x2++) {
if(copy1%2==0) {
long newconf=cc[k][j]+powe[x2-1];
if ((pd[x2][newconf]<pd[x1][cc[k][j]]+d[x1][x2]) && (bagat[x2])) {
pd[x2][newconf]=pd[x1][cc[k][j]]+d[x1][x2];
prev[x2][newconf]=x1*1000000+cc[k][j];
}
if ((pd[x2][newconf]>=maxi) && (bagat[x2])) {
maxi=pd[x2][newconf];
maxx=x2;
maxy=newconf;
}
}
copy1/=2;
}
}
}
copy/=2;
}
}
int bb[nmax];
bb[0]=0;
while(prev[maxx][maxy]!=0) {
bb[++bb[0]]=maxx;
int maux=maxx;
maxx=prev[maxx][maxy]/1000000;
maxy=prev[maux][maxy]%1000000;
}
bb[++bb[0]]=maxx;
bb[bb[0]+1]=0;
for(long i=bb[0];i>=1;i--) {
long n2=bb[i];
long n1=bb[i+1];
for(long j=1+d[n1][n2];j<=cate[n2];j++) printf("%c",a[n2][j]);
}
return 0;
}