Pagini recente » Cod sursa (job #478727) | Cod sursa (job #2112658) | Cod sursa (job #1102425) | Cod sursa (job #863487) | Cod sursa (job #1464037)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 2e9, NMAX = 18, LENMAX = 30005;
int len[NMAX + 5];
int match[NMAX + 5][NMAX + 5];
char str[NMAX + 5][LENMAX];
int lmin[1 << NMAX][NMAX + 5];
int dp[1 << NMAX][NMAX + 5];
char sol[LENMAX * NMAX];
vector <int> res;
int kmp (int a, int b) {
int i, p, pi[LENMAX];
p = 0;
pi[1] = 0;
for(i = 2; i <= len[b]; ++ i) {
while(p && str[b][p + 1] != str[b][i])
p = pi[p];
if(str[b][p + 1] == str[b][i])
++ p;
pi[i] = p;
}
p = 0;
for(i = 1; i <= len[a]; ++ i) {
while(p && str[b][p + 1] != str[a][i])
p = pi[p];
if(str[b][p + 1] == str[a][i])
++ p;
}
return p;
}
bool testBit (int x, int bit) {
return x & (1 << bit);
}
int main() {
//freopen("adn.in", "r", stdin);
//freopen("adn.out", "w", stdout);
int i, n, j, subset, last, l, newSet;
scanf("%d\n", &n);
for (i = 0; i < n; ++ i) {
scanf("%s", str[i] + 1);
len[i] = strlen(str[i] + 1);
lmin[1 << i][i] = len[i];
}
for (i = 0; i < n; ++ i)
for (j = 0; j < n; ++ j)
if (i != j)
match[i][j] = kmp(i, j);
for (subset = 1; subset < (1 << n); ++ subset)
for (last = 0; last < n; ++ last)
if (testBit(subset, last) && lmin[subset][last])
for (i = 0; i < n; ++ i)
if (!testBit(subset, i)) {
newSet = subset | (1 << i);
if (lmin[newSet][i] == 0 || lmin[newSet][i] > lmin[subset][last] + len[i] - match[last][i])
lmin[newSet][i] = lmin[subset][last] + len[i] - match[last][i],
dp[newSet][i] = last;
// fprintf(stderr, "%d %d - %d\n", newSet, i, lmin[newSet][i]);
}
subset = (1 << n) - 1;
l = INF;
for (i = 0; i < n; ++ i)
if (lmin[subset][i] && lmin[subset][i] < l) {
l = lmin[subset][i];
last = i;
}
while (subset) {
i = dp[subset][last];
res.push_back(last);
subset ^= (1 << last);
last = i;
}
reverse(res.begin(), res.end());
l = 0;
strcat(sol, str[res[0]] + 1);
for (i = 1; i < res.size(); ++ i)
strcat(sol, str[res[i]] + 1 + match[res[i - 1]][res[i]]);
printf("%s\n", sol);
return 0;
}