Pagini recente » Cod sursa (job #276093) | Cod sursa (job #566617) | Cod sursa (job #276695) | Cod sursa (job #631799) | Cod sursa (job #1012196)
#include <stdio.h>
#include <string.h>
char x[20][31000];
int len[20], extra[20][20];
int bad, dp[20][1 << 20], gone[20][1 << 20], fail[69000];
char X[69000];
void rec(int mask, int last) {
int i, pmask = gone[last][mask];
if (pmask == 0) {
for (int i = 1; i <= len[last]; ++i)
printf("%c", x[last][i]);
return ;
}
for (i = 1; ; ++i)
if (pmask & (1 << (i - 1)) && (bad & (1 << (i - 1))) == 0)
if (dp[i][pmask] + extra[i][last] == dp[last][mask])
break;
rec(pmask, i);
for (int j = len[last] - extra[i][last] + 1; j <= len[last]; ++j)
printf("%c", x[last][j]);
}
int main() {
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
int N;
scanf("%d\n", &N);
for (int i = 1; i <= N; ++i) {
gets(x[i] + 1);
len[i] = strlen(x[i] + 1);
}
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j) {
if (i == j)
continue;
int n = 0;
for (int k = 1; k <= len[j]; ++k)
X[++n] = x[j][k];
X[++n] = '#';
for (int k = 1; k <= len[i]; ++k)
X[++n] = x[i][k];
for (int k = 2; k <= n; ++k) {
int pf = fail[k - 1];
while (1) {
if (X[pf + 1] == X[k]) {
++pf;
break;
}
if (pf == 0)
break;
pf = fail[pf];
}
fail[k] = pf;
}
extra[i][j] = len[j] - fail[n];
for (int k = 1; k <= n; ++k)
if (fail[k] == len[j]) {
bad ^= (1 << (j - 1));
break;
}
}
for (int i = 1; i <= N; ++i)
for (int mask = 0; mask < (1 << N); ++mask)
dp[i][mask] = 1 << 30;
for (int i = 1; i <= N; ++i)
dp[i][1 << (i - 1)] = len[i];
for (int mask = 1; mask < (1 << N); ++mask)
for (int i = 1; i <= N; ++i)
if (dp[i][mask] != 1 << 30)
for (int j = 1; j <= N; ++j)
if ((mask & (1 << (j - 1))) == 0 && (bad & (1 << (j - 1))) == 0)
if (dp[i][mask] + extra[i][j] < dp[j][mask ^ (1 << (j - 1))]) {
dp[j][mask ^ (1 << (j - 1))] = dp[i][mask] + extra[i][j];
gone[j][mask ^ (1 << (j - 1))] = mask;
}
int go = 1;
for (int i = 2; i <= N; ++i)
if (dp[i][((1 << N) - 1) ^ bad] < dp[go][((1 << N) - 1) ^ bad])
go = i;
rec(((1 << N) - 1) ^ bad, go);
return 0;
}