Pagini recente » Cod sursa (job #2841874) | Cod sursa (job #1299998) | Cod sursa (job #2735876) | Cod sursa (job #2049814) | Cod sursa (job #1257614)
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
#define MAX 30105
#define MAXN 20
#define INF INT_MAX/2;
int a[1<<MAXN][MAXN];
int p[1<<MAXN][MAXN];
char v[MAXN][MAX];
int pi[MAX], C[MAXN][MAXN];
int dr, st[MAXN+2];
int ve[MAXN], viz[MAXN];
int kmp(char a[], char b[])
{
int n=strlen(a+1);
int m=strlen(b+1);
pi[1]=0;
int i, k;
for(i=2;i<=n;i++)
{
k=pi[i-1];
while(k!=0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
{
k++;
}
pi[i]=k;
}
k=0;
for(i=1;i<=m;i++)
{
while(k!=0 && a[k+1]!=b[i])
{
k=pi[k];
}
if(a[k+1]==b[i])
{
k++;
}
if(k==n)
{
return 0;
}
}
return n-k;
}
int main()
{
int n, i, j, k, val, ind, nod, m;
fin>>n;
for(i=0;i<n;i++)
{
fin>>(v[i]+1);
}
l:
for(i=0;i<n;i++)
{
viz[i]=0;
for(j=0;j<n;j++)
{
if(i==j)
continue;
C[i][j]=kmp(v[i], v[j]);
if(!C[i][j])
viz[i]=1;
}
}
dr=0;
for(i=0;i<n;i++)
{
if(!viz[i])
memcpy(v[dr++], v[i], sizeof(v[i]));
}
if(dr!=n)
{
n=dr;
goto l;
}
dr=0;
for(i=1;i<(1<<n);i++)
{
for(j=0;j<n;j++)
p[i][j]=-1;
if((i&(i-1))==0)
continue;
for(j=0;j<n;j++)
{
if((i&(1<<j))==0)
continue;
a[i][j]=INF;
for(k=0;k<n;k++)
{
if((i&(1<<k))==0)
continue;
if(k==j)
continue;
if(C[k][j]+a[i-(1<<j)][k]<a[i][j])
{
a[i][j]=C[k][j]+a[i-(1<<j)][k];
p[i][j]=k;
}
}
}
}
val=INF;
for(i=0;i<n;i++)
{
if(a[(1<<n)-1][i]<val)
{
val=a[(1<<n)-1][i];
ind = i;
}
}
st[++dr]=ind;
nod=(1<<n)-1;
while(ind!=-1)
{
st[++dr]=p[nod][ind];
nod=(nod)-(1<<ind);
ind=st[dr];
}
fout << v[st[1]]+1;
for(i=2;i<=n;i++)
{
m=strlen(v[st[i]]+1);
for(j=m-C[st[i]][st[i-1]]+1;j<=m;j++)
fout << v[st[i]][j];
}
}