Pagini recente » Cod sursa (job #1170259) | Cod sursa (job #392646) | Cod sursa (job #1168170) | Cod sursa (job #570166) | Cod sursa (job #791768)
Cod sursa(job #791768)
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 19;
const int M = 30005;
const int INF = 0x3f3f3f3f;
int n, s;
int pi[N], len[N];
int d[1 << N][N], reconst[1 << N][N];
int shorter[N][N];
char sol[N * M];
char text[N][M];
void read() {
assert(freopen("adn.in", "r", stdin) != NULL);
assert(freopen("adn.out", "w", stdout) != NULL);
assert(scanf("%d", &n) == 1);
for (int i = 0; i < n; ++i) {
assert(scanf(" %s ", text[i] + 1) == 1);
len[i] = strlen(text[i] + 1);
}
}
void prefix(char pattern[]) {
memset(pi, 0, sizeof(pi));
int p = 0;
int n = strlen(pattern + 1);
for (int i = 2; i <= n; ++i) {
while (p > 0 && pattern[p + 1] != pattern[i])
p = pi[p];
if (pattern[p + 1] == pattern[i])
++p;
pi[i] = p;
}
}
int match(char pattern[], char text[]) {
int p = 0;
int n = strlen(text + 1);
int m = strlen(pattern + 1);
for (int i = 1; i <= n; ++i) {
while (p > 0 && pattern[p + 1] != text[i])
p = pi[p];
if (pattern[p + 1] == text[i])
++p;
if (p == m)
return -1;
}
return p;
}
void preprocesare_kmp() {
for (int i = 0; i < n; ++i) {
prefix(text[i]);
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
int x = match(text[i], text[j]);
if (x == -1) {
memcpy(text[i], text[n - 1], sizeof(text[n - 1]));
len[i] = len[n - 1];
--i;
--n;
break;
}
}
}
/*for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
prefix(text[j]);
shorter[i][j] = match(text[i], text[j]);
}*/
}
void intializare() {
for (int i = 0; i < (1 << n); ++i)
for (int j = 0; j <= n; ++j)
d[i][j] = INF;
for (int i = 0; i < n; ++i)
d[1 << i][i] = len[i];
}
void dinamica() {
intializare();
for (int conf = 1; conf < (1 << n); ++conf)
for (int last = 0; last < n; ++last) {
for (int newLast = 0; newLast < n; ++newLast) {
if (last == newLast || (conf & (1 << newLast)))
continue;
if (d[conf][last] + len[newLast] - shorter[last][newLast] < d[conf | (1 << newLast)][newLast]) {
d[conf | (1 << newLast)][newLast] = d[conf][last] + len[newLast] - shorter[last][newLast];
reconst[conf | (1 << newLast)][newLast] = last;
}
}
}
}
void reconstituire() {
int last = 0;
for (int i = 0; i < n; ++i)
if (d[1 << n][i] < d[1 << n][last])
last = i;
int conf = (1 << n) - 1;
while (conf) {
int newLast = reconst[conf][last];
for (int i = len[last]; i > shorter[newLast][last]; --i)
sol[++s] = text[last][i];
conf &= ~(1 << last);
last = newLast;
}
}
void write() {
for (int i = s; i > 0; --i)
printf("%c", sol[i]);
}
int main() {
read();
preprocesare_kmp();
//fprintf(stderr, "%d", n);
//for (int i = 0; i < 4; ++i) {
// printf("%s ", text[i] + 1);
//printf("\n");
//}
dinamica();
reconstituire();
write();
}