Pagini recente » Borderou de evaluare (job #72433) | Borderou de evaluare (job #1593350) | Borderou de evaluare (job #1911194) | Borderou de evaluare (job #2034990) | Cod sursa (job #576662)
Cod sursa(job #576662)
#include <cstdio>
#include <cstring>
#define nmax 25
#define lmax 30015
#define nrstari (1<<18)+15
int n, toate, lungime [nmax], pi [nmax] [lmax], potrivire [nmax] [nmax], r [nmax] [nrstari];
bool ok [nmax];
char a [nmax] [lmax];
int prev [nmax] [nrstari];
void scan ()
{
int i;
scanf ("%d", &n);
for (i=0; i < n; ++i)
scanf ("%s", a [i]+1);
}
void calc_pi (int k)
{
int i, q=0;
pi [k] [1]=0;
for (i=2; a [k] [i]; ++i)
{
while (q && a [k] [i] != a [k] [q+1])
q=pi [k] [q];
if (a [k] [i] == a [k] [q+1]) ++q;
pi [k] [i]=q;
}
lungime [k]=i-1;
}
int kmp (int B, int A)
{
int i, q=-1;
for (i=1; a [B] [i]; ++i)
{
while (q && a [A] [q+1] != a [B] [i])
q=pi [A] [q];
if (a [A] [q+1] == a [B] [i]) ++q;
if (q == lungime [A])
return -1;
}
return q;
}
void calc_potrivire ()
{
int i, j;
for (i=0; i < n; ++i)
calc_pi (i);
for (i=0; i < n; ++i)
for (j=0; j < n; ++j)
{
if (i == j) continue;
potrivire [i] [j]=kmp (i, j);
if (potrivire [i] [j] == -1)
ok [j]=true;
}
for (i=0; i < n; ++i)
for (j=0; j < i; ++j)
if (potrivire [i] [j] == -1 && potrivire [i] [j] == potrivire [j] [i])
ok [j]=false;
}
int rez ()
{
int i, j, k, stari=1<<n;
for (i=0; i < stari; ++i)
for (j=0; j < n; ++j)
if (i & (1<<j))
{
if (ok [j])
continue;
for (k=0; k < n; ++k)
if ((k != j) && (i & (1 << k)))
{
if (r [j] [i] <= r [k] [i^(1<<j)] + potrivire [k] [j])
{
r [j] [i]=r [k] [i^(1<<j)] + potrivire [k] [j];
prev [j] [i]=k;
}
}
}
int m=-1, l=0;
toate=(1<<n)-1;
for (i=0; i < n; ++i)
if (ok [i])
toate ^= 1<<i;
for (i=0; i < n; ++i)
if (m <= r [i] [toate])
{
m=r [i] [toate];
l=i;
}
return l;
}
void print (int stare, int l)
{
if (stare == 0) return;
if (r [l] [stare] == 0)
{
int i;
for (i=0; i < n; ++i)
if (stare & (1 << i))
printf ("%s", a [i]+1);
return;
}
print (stare^(1<<l), prev [l] [stare]);
printf ("%s", a [l]+1+potrivire [prev [l] [stare]] [l]);
}
int main ()
{
freopen ("adn.in", "r", stdin);
freopen ("adn.out", "w", stdout);
scan ();
calc_potrivire ();
int l=rez ();
print (toate, l);
return 0;
}