Pagini recente » Cod sursa (job #1181780) | Cod sursa (job #2471631) | Cod sursa (job #886585) | Cod sursa (job #1215957) | Cod sursa (job #1067591)
#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;
int N;
char adn[19][30007];
int F[19][30007];
int M[19];
void build_failure() {
for (int k = 0; k < N; ++k) {
int* FF = F[k];
char* pat = adn[k];
FF[0] = FF[1] = 0;
for (int i = 2; i <= M[k]; ++i) {
FF[i] = 0;
int j = FF[i-1];
while (j) {
if (pat[j] == pat[i-1]) {
FF[i] = j + 1; break;
}
j = FF[j];
}
}
}
}
int hash_kmp[20][20];
int kmp(int k1, int k2) {
if (hash_kmp[k1][k2]) return hash_kmp[k1][k2] - 1;
// k1 ... k2
int& best = hash_kmp[k1][k2];
int i = 0, j = 0;
char* text = adn[k1];
char* pat = adn[k2];
while (1) {
if (i == M[k1]) break;
if (text[i] == pat[j]) {
++i; ++j;
if (j > best && i == M[k1]) best = j;
if (j == M[k2]) { best = M[k2] + 1; return best - 1;}
} else {
if (j > 0) j = F[k2][j];
else ++i;
}
}
best++;
return best - 1;
}
int dp[1<<18][18];
int go(int mask, int p) {
if (mask + 1 == (1<<N)) return 0;
if (dp[mask][p]) return dp[mask][p];
int& ret = dp[mask][p];
ret = 30000 * N;
for (int i = 0; i < N; ++i) if (!(mask & (1 << i))) {
int now = M[i] - kmp(p, i) + go(mask | (1<<i), i);
if (now < ret) ret = now;
}
return ret;
}
int main() {
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
scanf("%s", &adn[i]);
M[i] = strlen(adn[i]);
}
build_failure();
int best = 30000 * N + 1;
int mask = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j) if (i != j) if (kmp(i, j) == M[j]) mask |= (1 << j);
int last_i = 0;
for (int i = 0; i < N; ++i) if (!(mask & (1 << i))) {
int now = go(mask | (1<<i), i) + M[i];
if (now < best) best = now, last_i = i;
}
printf("%s", adn[last_i]);
best -= M[last_i]; mask |= (1<<last_i);
while (mask + 1 != (1<<N)) {
for (int i = 0; i < N; ++i) if (!(mask & (1<<i))) {
int now = go(mask | (1<<i), i) + M[i] - kmp(last_i, i);
if (now == best) {
best -= M[i] - kmp(last_i, i);
printf("%s", adn[i] + kmp(last_i, i));
last_i = i; mask |= (1<<i);
break;
}
}
}
printf("\n");
return 0;
}