Pagini recente » Cod sursa (job #984234) | Cod sursa (job #1619164) | Cod sursa (job #1744862) | Cod sursa (job #2907606) | Cod sursa (job #1169649)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 18, L = 30001, inf = 0x3f3f3f3f;
char sir[N][L];
int best[1 << N][N], cost[N][N], pi[L], n;
ifstream in("adn.in");
ofstream out("adn.out");
int getCost(char a[], char b[]){
int sizeB = strlen(b + 1);
pi[0] = -1; pi[1] = 0;
for (int i = 1 ; b[i] ; i++){
pi[i] = pi[i - 1];
while ( pi[i] >= 0 && b[ pi[i] + 1 ] != b[i] )
pi[i] = pi[ pi[i] ];
pi[i]++;
}
int k = 0;
for (int i = 1 ; k != sizeB && a[i] ; i++){
while ( k >= 0 && b[k + 1] != a[i] )
k = pi[k];
k++;
}
return sizeB - k;
}
inline int getCost(int x, int y){
return getCost(sir[x], sir[y]);
}
inline bool valid(int mask, int x, int y){
return x != y && ( mask & (1 << x) ) && ( mask & (1 << y) );
}
bool isRelevant(int x){
int poz = 0;
while (poz < n && (poz == x || getCost(poz, x) != 0))
poz++;
return poz == n;
}
void print(int mask, int k){
int p = 0;
while ( p < n && ( p == k || ( mask & (1 << p) ) == 0 || best[mask][k] != best[mask ^ (1 << k)][p] + cost[p][k] ) )
p++;
if (p != n){
print(mask ^ (1 << k), p);
out << (sir[k] + strlen(sir[k] + 1) + 1 - cost[p][k]);
} else
out << sir[k] + 1;
}
int main(){
in >> n;
for (int i = 0 ; i < n ; i++)
in >> (sir[i] + 1);
int nr = 0;
for (int i = 0 ; i < n ; i++)
if ( isRelevant(i) )
strcpy(sir[nr++] + 1, sir[i] + 1);
n = nr;
memset(best, inf, sizeof(best));
for (int i = 0 ; i < n ; i++)
best[1 << i][i] = strlen( sir[i] + 1 );
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++)
cost[i][j] = getCost(i, j);
for (int i = 0 ; i < (1 << i) ; i++)
for (int j = 0 ; j < n ; j++)
for (int k = 0 ; k < n ; k++)
if ( valid(i, j, k) )
best[i][j] = min(best[i][j], best[i ^ (1 << j)][k] + cost[k][j]);
int k = 0, mask = (1 << n) - 1;
for (int i = 1 ; i < n ; i++)
if ( best[mask][i] < best[mask][k] )
k = i;
print(mask, k);
out << '\n';
return 0;
}