Pagini recente » Cod sursa (job #3174853) | Cod sursa (job #1818948) | Cod sursa (job #138767) | Cod sursa (job #2279676) | Cod sursa (job #434145)
Cod sursa(job #434145)
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LIM (1<<18)+5
#define MAX 30005
#define DIM 20
int best[LIM][DIM],ant[LIM][DIM],dst[DIM][DIM];
int lg[DIM],pi[DIM],newn[DIM];
int n,m,cost,rez,poz;
char buff[DIM][MAX];
bool inside[DIM];
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
{
scanf ("%s",buff[i]+1);
lg[i]=strlen (buff[i]+1);
}
}
inline void prefix (int x)
{
int i,k;
for (k=0, i=2; i<=lg[x]; ++i)
{
for ( ; k && buff[x][k+1]!=buff[x][i]; k=pi[k]);
if (buff[x][k+1]==buff[x][i])
++k;
pi[i]=k;
}
}
inline int kmp (int x,int y)
{
int i,k,ok;
for (ok=k=0, i=1; i<=lg[y]; ++i)
{
for ( ; k && buff[x][k+1]!=buff[y][i]; k=pi[k]);
if (buff[x][k+1]==buff[y][i])
++k;
if (k==lg[x])
ok=1;
cost=k;
}
return ok;
}
void init ()
{
int i,j;
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (i!=j)
{
prefix (i);
cost=0;
if (kmp (i,j))
inside[i]=1;
dst[j][i]=cost;
}
for (i=1; i<=n; ++i)
if (!inside[i])
newn[++m]=i;
}
void print (int x,int lv)
{
int i;
if (!lv)
return ;
print (ant[lv][x],lv^(1<<(x-1)));
for (i=dst[newn[ant[lv][x]]][newn[x]]+1; i<=lg[newn[x]]; ++i)
printf("%c",buff[newn[x]][i]);
}
void solve ()
{
int i,j,k;
memset (best,INF,sizeof (best));
for (i=1; i<=m; i++)
best[1<<(i-1)][i]=lg[newn[i]];
for (i=0; i<(1<<m); ++i)
for (j=1; j<=m; ++j)
if (i&(1<<(j-1)))
for (k=1; k<=m; ++k)
if (!(i&(1<<(k-1))))
if (best[i^(1<<(k-1))][k]>best[i][j]+lg[newn[k]]-dst[newn[j]][newn[k]])
{
best[i^(1<<(k-1))][k]=best[i][j]+lg[newn[k]]-dst[newn[j]][newn[k]];
ant[i^(1<<(k-1))][k]=j;
}
rez=INF;
for (i=1; i<=m; ++i)
if (best[(1<<m)-1][i]<rez)
{
rez=best[(1<<m)-1][i];
poz=i;
}
print (poz,(1<<m)-1);
}
int main ()
{
freopen ("adn.in","r",stdin);
freopen ("adn.out","w",stdout);
read ();
init ();
solve ();
}