Pagini recente » Cod sursa (job #465451) | Cod sursa (job #2118755) | Cod sursa (job #96326) | Cod sursa (job #375118) | Cod sursa (job #1538457)
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <fstream>
#define FILEIN "adn.in"
#define FILEOUT "adn.out"
using namespace std;
const int INF = 0x3f3f3f3f;
const int NMAX = 18;
const int LMAX = 30011;
int S[NMAX][NMAX];
char A[NMAX][LMAX];
int D[1<<NMAX][NMAX];
int T[1<<NMAX][NMAX];
int n;
vector<int> Sol;
void prefix(char x[], int p[]) {
int X = strlen(x);
p[0] = -1;
int k = -1;
for (int i = 1; i < X; i++) {
while (k != -1 && x[k + 1] != x[i])
k = p[k];
if (x[k + 1] == x[i])
k++;
p[i] = k;
}
}
int kmp(char x[], char y[]) {
int p[LMAX];
prefix(x, p);
int X = strlen(x);
int Y = strlen(y);
int k = -1;
for (int i = 0; i < Y; i++) {
while (k != -1 && x[k + 1] != y[i])
k = p[k];
if (x[k + 1] == y[i])
k++;
if (k == X - 1)
break;
}
return X - 1 - k;
}
void hamilton() {
memset(D, INF, sizeof(D));
for (int i = 0; i < n; i++)
D[(1 << i)][i] = strlen(A[i]);
for (int i = 1; i < (1 << n); i++) {
for (int k = 0; k < n; k++) {
if (i & (1 << k)) {
for (int l = 0; l < n; l++) {
if (i & (1 << l))
continue;
if (D[i | (1 << l)][l] > D[i][k] + S[k][l]) {
D[i | (1 << l)][l] = D[i][k] + S[k][l];
T[i | (1 << l)][l] = k;
}
}
}
}
}
int min = INF, idx = -1;
for (int k = 0; k < n; k++) {
if (D[(1 << n) - 1][k] < min) {
min = D[(1 << n) - 1][k];
idx = k;
}
}
int tmp = (1 << n) - 1;
while (tmp != 0) {
Sol.push_back(idx);
int aux = idx;
idx = T[tmp][idx];
tmp -= (1 << aux);
}
reverse(Sol.begin(), Sol.end());
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
cin.sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
S[i][j] = kmp(A[j], A[i]);
}
}
hamilton();
cout << A[Sol[0]];
for (int i = 1; i < Sol.size(); i++) {
cout << A[Sol[i]] + strlen(A[Sol[i]]) - S[Sol[i-1]][Sol[i]];
}
cout << '\n';
return 0;
}