Pagini recente » Cod sursa (job #2472806) | Cod sursa (job #2824395) | Cod sursa (job #2323139) | Cod sursa (job #2824408) | Cod sursa (job #797916)
Cod sursa(job #797916)
#include<cstdio>
#include<cassert>
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n, cost[20][20], isin[20];
string t[20];
int cmp(string x, string y){
return x.size() > y.size();
}
int pr[30010], dp[30010];
void pref(string x, int sz){
for(int i = 0; i < sz; ++i)
dp[i] = 0;
for(int i = 0; i < x.size(); ++i)
pr[i] = 0;
for(int i = 1; i < x.size(); ++i){
int p = i;
do{
--p;
p = pr[p];
if(x[i] == x[p]){
pr[i] = pr[p] + 1;
break;
}
}while(p != 0);
}
}
int kmp(string x, string y){
pref(y, x.size());
for(int i = 0; i < x.size(); ++i){
int p = i;
do{
--p;
p = pr[p];
if(x[i] == y[p]){
dp[i] = dp[p] + 1;
break;
}
}while(p!= 0);
}
return y.size() - dp[x.size() - 1];
}
void read(){
assert(freopen("adn.in", "r", stdin));
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> t[i];
sort(t + 1, t + n + 1, cmp);
for(int i = 2; i <= n; ++i){
for(int j = 1; j < i; ++j)
if(kmp(t[j], t[i]) == 0){
for(int k = i; k < n; ++k)
t[k] = t[k + 1];
--n;
--i;
break;
}
}
for(int i = 2; i <= n; ++i)
for(int j = 1; j < i; ++j){
cost[j][i] = kmp(t[j], t[i]);
cost[i][j] = kmp(t[i], t[j]);
}
}
string ans;
int d[19][300000], dad[19][300000];
void solve(){
int inf = 1000000000;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= 1 << n; ++j)
d[i][j] = inf;
for(int i = 1; i <= n; ++i)
d[i][1 << (i - 1)] = 0;
int lim = 1 << n;
for(int j = 0; j < lim; ++j){
for(int i = 1; i <= n; ++i){
for(int k = 1; k <= n; ++k)
if(j & (1 << (k - 1)));
else{
int x = j + (1 << (k - 1));
if(d[k][x] > d[i][j] + cost[i][k]){
dad[k][x] = i;
d[k][x] = d[i][j] + cost[i][k];
}
}
}
}
int p = inf, pos = 0;
for(int i = 1; i <= n; ++i)
if(d[i][lim - 1] < p){
pos = i;
p = d[i][lim - 1];
}
int k = pos, r = lim - 1;
vector<int> lol;
while(k){
lol.push_back(k);
int aux = k;
k = dad[k][r];
r = r - (1 << (aux - 1));
}
for(int i = lol.size() - 1; i >= 0; --i)
ans += t[lol[i]];
}
void write(){
assert(freopen("adn.out", "w", stdout));
cout << ans;
}
int main(){
read();
solve();
write();
return 0;
}