Pagini recente » Cod sursa (job #555023) | Cod sursa (job #511436) | Borderou de evaluare (job #565584) | Cod sursa (job #2813521) | Cod sursa (job #1071222)
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 20
#define maxl 30005
#define maxm 1<<18
#define inf 0x3f3f3f3f
using namespace std;
int n,nr,sol,E;
int len[maxn],p[maxl],used[maxn];
int c[maxn][maxn],d[maxn][maxn],node[maxn],rnode[maxn];
int s[maxm][maxn],father[maxm][maxn];
char a[maxn][maxl];
void read()
{
scanf("%d\n",&n);
for(int i=1;i<=n;i++)
{
scanf("%s\n",a[i]+1);
len[i]=strlen(a[i]+1);
}
}
int kmp(int x,int y)
{
int k=0;
memset(p,0,sizeof(p));
p[1]=0;
for(int i=2;i<=len[x];i++)
{
while(k && a[x][k+1]!=a[x][i]) k=p[k];
if(a[x][k+1]==a[x][i]) k++;
p[i]=k;
}
k=0;
for(int i=1;i<=len[y];i++)
{
while(k && a[x][k+1]!=a[y][i]) k=p[k];
if(a[x][k+1]==a[y][i]) k++;
if(k==len[x]) {used[x]=1; return -1;}
}
return k;
}
void init()
{
for(int i=1;i<=nr;i++)
for(int j=1;j<=nr;j++)
d[i][j]=0;
}
void build_graph()
{
int x,y;
for(int i=1;i<n;i++) if(!used[i])
for(int j=i+1;j<=n;j++) if(!used[j])
{
x=kmp(i,j); if(x==-1) break;
y=kmp(j,i); c[i][j]=y; c[j][i]=x;
}
for(int i=1;i<=n;i++) if(!used[i])
node[i]=++nr,rnode[nr]=i;
init();
for(int i=1;i<n;i++) if(!used[i])
for(int j=i+1;j<=n;j++) if(!used[j])
{
d[node[i]][node[j]]=c[i][j];
d[node[j]][node[i]]=c[j][i];
}
}
void det(int mask,int k)
{
int newm;
s[mask][k]=inf;
for(int i=0;(mask>>i);i++)
if( ((mask>>i)&1) )
{
newm=mask^(1<<(k-1));
if(s[newm][i+1]==-1) det(newm,i+1);
if(s[mask][k]>s[newm][i+1]+len[rnode[k]]-d[i+1][k])
{
s[mask][k]=s[newm][i+1]+len[rnode[k]]-d[i+1][k];
father[mask][k]=i+1;
}
}
}
void init_s()
{
for(int i=1;i<(1<<nr);i++)
for(int j=1;j<=nr;j++)
s[i][j]=-1;
for(int i=1;i<=nr;i++) s[1<<(i-1)][i]=len[rnode[i]];
memset(father,0,sizeof(father));
}
void solve()
{
sol=inf;
init_s();
for(int j=1;j<=nr;j++)
{
det((1<<nr)-1,j);
if(s[(1<<nr)-1][j]<sol)
{
sol=s[(1<<nr)-1][j]; E=j;
}
}
}
void print(int m,int k)
{
int newm;
if(!father[m][k])
{
for(int i=1;i<=len[rnode[k]];i++)
printf("%c",a[rnode[k]][i]);
return;
}
newm=m^(1<<(k-1));
print(newm,father[m][k]);
for(int i=d[father[m][k]][k]+1;i<=len[rnode[k]];i++)
printf("%c",a[rnode[k]][i]);
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
read();
build_graph();
solve();
print((1<<nr)-1,E);
fclose(stdin);
fclose(stdout);
return 0;
}