Pagini recente » Cod sursa (job #2273656) | Cod sursa (job #2400930) | Cod sursa (job #85819) | Cod sursa (job #967926) | Cod sursa (job #1744340)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 20
#define MAXLEN 30050
using namespace std;
char s[MAXN][MAXLEN];
int n, dist[MAXN][MAXN];
int pref[MAXLEN];
int memo[1<<MAXN][MAXN], nxt[1<<MAXN][MAXN];
void citire()
{
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
gets(s[i]+1);
}
/// cel mai lung prefix al lui A care sa fie sufix lui B
int KMP(char a[], char b[])
{
int al = strlen(a+1), bl = strlen(b+1);
int pi = 0;
pref[1] = 0;
for (int i = 2; i <= al; i++) {
while (pi && a[i] != a[pi+1])
pi = pref[pi];
if (a[i] == a[pi+1])
pi++;
pref[i] = pi;
}
pi = 0;
for (int i = 2; i <= bl; i++) {
while (pi && b[i] != a[pi+1])
pi = pref[pi];
if (b[i] == a[pi+1])
pi++;
}
return pi;
}
int toDel[MAXN];
int included(char a[], char b[])
{
int al = strlen(a+1), bl = strlen(b+1);
int pi = 0;
pref[1] = 0;
for (int i = 2; i <= al; i++) {
while (pi && a[i] != a[pi+1])
pi = pref[pi];
if (a[i] == a[pi+1])
pi++;
pref[i] = pi;
}
pi = 0;
for (int i = 2; i <= bl; i++) {
while (pi && b[i] != a[pi+1])
pi = pref[pi];
if (b[i] == a[pi+1])
pi++;
if (pi == al)
return 1;
}
return 0;
}
void prepare()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && !toDel[i] && !toDel[j] && strlen(s[i]+1) <= strlen(s[j]+1) &&
included(s[i], s[j]))
toDel[i] = 1;
for (int i = 1; i <= n; i++)
if (toDel[i]) {
swap(toDel[i], toDel[n]);
swap(s[i], s[n]);
n--;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j) continue;
int c = KMP(s[j], s[i]);
dist[i-1][j-1] = c;
}
memset(memo, -1, sizeof memo);
}
void debug()
{
for (int i = 0; i < n; i++, printf("\n"))
for (int j = 0; j < n; j++)
printf("%d ", dist[i][j]);
}
/// Lant hamiltonian de cost maxim
int hamilton(int nod, int mask)
{
if (memo[mask][nod] != -1)
return memo[mask][nod];
if (mask == (1<<nod))
return 0;
mask ^= (1 << nod);
int best = -1;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) continue;
int crt = dist[nod][i] + hamilton(i, mask);
if (crt > best) {
best = crt;
nxt[mask][nod] = i;
}
}
memo[mask][nod] = best;
return best;
}
void afisare(int start)
{
printf("%s", s[start+1]+1);
int mask = (1<<n)-1-(1<<start);
for (int crt = start; mask; ) {
int urm = nxt[mask][crt];
printf("%s", s[urm+1]+1+dist[crt][urm]);
crt = urm;
mask -= (1 << crt);
}
}
int main()
{
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
citire();
prepare();
//debug();
int best = -1, nod;
for (int i = 0; i < n; i++) {
int crt = hamilton(i, (1<<n)-1);
if (crt > best) {
best = crt;
nod = i;
}
}
afisare(nod);
return 0;
}