Pagini recente » Cod sursa (job #143821) | Cod sursa (job #1273443) | Cod sursa (job #1051769) | Cod sursa (job #8129) | Cod sursa (job #1009797)
#include<stdio.h>
#include<math.h>
#include<string.h>
int pr[30][30],pi[30][30],l[30],d[265000][23],p[30],xu[265000][23],yu[265000][23];
char a[23][30005],s[550000];
bool t[30];
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
int n,i,x,j,q,m=1,y,z,w,lg,u,sn,df;
scanf("%d\n",&n);
p[0]=1;
for(i=1;i<=n;i++)
{p[i]=p[i-1]*2;
gets(a[i]+1);
l[i]=strlen(a[i]+1);
pi[i][1]=x=0;
for(j=2;j<=l[i];j++)
{
while(a[i][x+1]!=a[i][j] && x>0)
{
x=pi[i][x];
}
if(a[i][x+1]==a[i][j])
x++;
pi[i][j]=x;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(j!=i)
{
x=0;
for(q=1;q<=l[j];q++)
{
while(a[i][x+1]!=a[j][q] && x>0)
{
x=pi[i][x];
}
if(a[i][x+1]==a[j][q])
x++;
if(x==l[i])
break;
}
if(q!=l[j]+1)
{
t[i]=1;
break;
}
pr[i][j]=x;
}
for(i=1;i<=n;i++)
if(t[i]==1)
{m=m/2;
for(j=i+1;j<=n;j++)
{
l[j-1]=l[j];
t[j-1]=t[j];
strcpy(a[j-1]+1,a[j]+1);
for(q=1;q<=l[j];q++)
pr[j-1][q-1]=pr[j][q];
}
n--;
i--;
}
//no' deci pana aici e bine
m=p[n]-1;
for(i=1;i<=m;i++)
{
w=i;
while(w!=0)
{
lg=log2(w & (-w))+1;
x=i-(w & (-w));
w=w-(w & (-w));
y=z=0;
for(q=1;q<=n;q++)
if(d[x][q]!=0)
if((d[x][q]-pr[lg][q]<y || y==0))
{
y=d[x][q];
z=q;
}
xu[i][lg]=x;
yu[i][lg]=z;
d[i][lg]=y+l[lg]-pr[lg][z];
}
}
w=d[m][1];
for(i=2;i<=n;i++)
if(d[m][i]<w)
{
w=d[m][i];
j=i;
}
x=m;
y=j;
sn=df=0;
while(x!=0 && y!=0)
{
for(i=l[y]-df;i>=1;i--)
{
sn++;
s[sn]=a[y][i];
}
df=pr[y][yu[x][y]];
j=xu[x][y];
y=yu[x][y];
x=j;
}
for(i=sn;i>=1;i--)
printf("%c",s[i]);
printf("\n");
return 0;
}