Pagini recente » Cod sursa (job #403925) | Cod sursa (job #2002252) | Cod sursa (job #920514) | Cod sursa (job #2204448) | Cod sursa (job #751464)
Cod sursa(job #751464)
#include<cstdio>
#include<cstring>
using namespace std;
int nr,nr1,mini,n,i,j,k,p,l[20],c[20][20],ap[20],d[20][20],x[20],s[20];
char a[20][30002],sm[600002];
int min(int a,int b)
{
if(a<b) return a;
return b;
}
int valid(int k)
{
if(s[k]>mini) return 0;
if(ap[x[k]]!=1) return 0;
return 1;
}
void back()
{
k=1;
x[k]=0;
ap[0]=1;
s[0]=0;
while(k>0)
{
while(x[k]<n&&k<=n-nr1)
{
ap[x[k]]--;
x[k]++;
ap[x[k]]++;
s[k]=s[k-1]+l[x[k]]-c[x[k-1]][x[k]];
if(valid(k))
{
if(k==n-nr1&&s[k]<mini)
{
mini=s[k];
nr=0;
for(i=1;i<=n-nr1;i++)
for(j=d[x[i-1]][x[i]];j<=l[x[i]];j++)
{
nr++;
sm[nr]=a[x[i]][j];
}
}
else
if(k<n-nr1)
{
k++;
x[k]=0;
ap[0]++;
}
}
}
ap[x[k]]--;
k--;
}
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
gets(a[i]+1);
l[i]=strlen(a[i]+1);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(i!=j)
{
if(l[i]==l[j]&&strcmp(a[i]+1,a[j]+1)==0) break;
else
if(l[i]<l[j])
{
for(p=1;p<=l[j]-l[i]+1;p++)
{
for(k=p;k<=p+l[i]-1;k++)
if(a[j][k]!=a[i][k-p+1]) break;
if(k>p+l[i]-1) break;
}
if(p<=l[j]-l[i]+1) break;
}
}
if(j<=n)
{
ap[i]=1;
nr1++;
}
}
for(j=1;j<=n;j++)
for(i=1;i<=n;i++)
if(ap[i]==0&&ap[j]==0&&i!=j)
{
for(p=1;p<=l[j];p++)
{
for(k=p;k<=min(l[j],p+l[i]-1);k++)
if(a[j][k]!=a[i][k-p+1]) break;
if(k>min(l[j],k+l[i]-1)) break;
}
c[j][i]=l[j]-p+1;
d[j][i]=c[j][i]+1;
}
for(i=1;i<=n;i++)
{
c[0][i]=0;
d[0][i]=1;
}
mini=1000000000;
back();
//printf("%s\n",sm+1);
for(i=1;i<=mini;i++)
printf("%c",sm[i]);
return 0;
}