Pagini recente » Cod sursa (job #171638) | preojiantrenament_4 | Cod sursa (job #1633192) | Cod sursa (job #2419818) | Cod sursa (job #1750169)
#include <bits/stdc++.h>
#define maxN 21
#define maxP (1 << 19) + 1
#define maxL 30005
#define inf 1000000000
using namespace std;
int n, m, all, ans, cost[maxN][maxN], dp[maxN][maxP + 1], len[maxN];
int v[maxL], path[maxN], p[maxN];
char s[maxN][maxL];
bool u[maxN];
void pref(int x)
{
memset(v, 0, sizeof(v));
v[1] = 0;
int i, k = 0;
for (i = 2; i <= len[x]; ++ i)
{
while (k > 0 && s[x][i]!= s[x][k + 1])
k = v[k];
if (s[x][i] == s[x][k + 1])
++ k;
v[i] = k;
}
}
void read()
{
int i;
freopen("adn.in", "r", stdin);
scanf("%d\n", &n);
for (i = 0; i < n; ++ i)
{
scanf("%s\n", s[i] + 1);
len[i] = strlen(s[i] + 1);
}
}
void init()
{
int i, j;
n = m;
all = (1 << n) - 1;
for (i = 0; i < n; ++ i)
for (j = 0; j <= all; ++ j)
dp[i][j] = inf;
dp[0][1] = 0;
ans = inf;
}
void get_cost()
{
int x, y;
for (x = 0; x < n; ++ x)
for (y = 0; y < n; ++ y)
if (x != y)
{
cost[y][x] = -1;
pref(y);
int i, k = 0, c;
for (i = 1; i <= len[x]; ++ i)
{
while (k > 0 && s[x][i] != s[y][k + 1])
k = v[k];
if (s[x][i] == s[y][k + 1])
++ k;
if (k == len[y])
{
cost[y][x] = 0;
u[y] = 1;
break;
}
if (i == len[x] && cost[y][x])
cost[y][x] = len[y] - k;
}
}
for (y = 0; y < n; ++ y)
if (!u[y])
p[m ++] = y;
}
void solve()
{
get_cost();
init();
int i, j, b;
for (i = 1; i <= all; ++ i)
if ((i & (i - 1)) == 0)
for (j = 0; j < n; ++ j)
if (i & (1 << j))
dp[j][i] = len[p[j]];
for (i = 1; i <= all; ++ i)
for (j = 0; j < n; ++ j)
if (i & (1 << j))
{
for (b = 0; b < n; ++ b)
if (!(i & (1 << b)) && dp[b][i ^ (1 << b)] > dp[j][i] + cost[p[b]][p[j]])
dp[b][i ^ (1 << b)] = dp[j][i] + cost[p[b]][p[j]];
if (i == all && dp[j][i] < ans)
{
ans = dp[j][i];
path[0] = j;
}
}
i = 0;
while (i < n - 1)
{
int j;
for (j = 0; j < n; ++ j)
if (dp[path[i]][all] == dp[j][all ^ (1 << path[i])] + cost[p[path[i]]][p[j]])
{
all ^= (1 << path[i]);
path[++ i] = j;
break;
}
}
}
void write()
{
int i, j, q = 1;
freopen("adn.out", "w", stdout);
//printf("%d\n", ans);
for (j = m - 1; j >= 0; -- j)
{
for (i = q; i <= len[p[path[j]]]; ++ i)
printf("%c", s[p[path[j]]][i]);
if (j)
q = len[p[path[j - 1]]] - cost[p[path[j - 1]]][p[path[j]]] + 1;
}
printf("\n");
}
int main()
{
read();
solve();
write();
return 0;
}