Pagini recente » Cod sursa (job #1019312) | Cod sursa (job #2369354) | Cod sursa (job #663972) | Cod sursa (job #1987365) | Cod sursa (job #799339)
Cod sursa(job #799339)
#include<cstdio>
#include<cassert>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int pi[30005];
void prefix(string &x){
pi[1] = 0;
for(int i = 2; i < x.size(); ++i){
int p = i - 1;
do{
p = pi[p];
if(x[i] == x[p + 1]){
pi[i] = p + 1;
break;
}
}while(p);
}
}
int mpref[30005];
int kmp_comp(string &x, string &y){
prefix(y);
for(int i = 1; i < x.size(); ++i)
mpref[i] = 0;
for(int i = 1; i < x.size(); ++i){
int p = mpref[i - 1];
if(x[i] == y[p + 1])
mpref[i] = p + 1;
else
do{
p = pi[p];
if(x[i] == y[p + 1]){
mpref[i] = p + 1;
break;
}
}while(p);
if(mpref[i] == y.size() - 1)
return 0;
}
return y.size() - 1 - mpref[x.size() - 1];
}
int cmp(string x, string y){
return x.size() > y.size();
}
int n, tab[22][22];
string giv[22];
void read(){
assert(freopen("adn.in", "r", stdin));
cin >> n;
for(int i = 1; i <= n; ++i){
string aux;
cin >> aux;
giv[i].push_back('#');
giv[i] = giv[i] + aux;
}
sort(giv + 1, giv + n + 1, cmp);
for(int i = 2; i <= n; ++i){
for(int j = 1; j < i; ++j)
if(kmp_comp(giv[j], giv[i]) == 0)
goto label;
continue;
label:for(int j = i; j < n; ++j)
giv[j] = giv[j + 1];
--i;
--n;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
tab[i][j] = kmp_comp(giv[i], giv[j]);
}
int dp[22][300005], dad[22][300005];
string ans;
void solve(){
int lim = 1 << n;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < lim; ++j)
dp[i][j] = 1000000000;
for(int i = 1; i <= n; ++i)
dp[i][1 << (i - 1)] = giv[i].size() - 1;
for(int i = 1; i < lim; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
if((1 << (k - 1)) & i);
else if(dp[j][i] + tab[j][k] < dp[k][i + (1 << (k - 1))]){
dp[k][i + (1 << (k - 1))] = dp[j][i] + tab[j][k];
dad[k][i + (1 << (k - 1))] = j;
}
vector<int> rec;
int men = 1000000000, ind = 0;
for(int i = 1; i <= n; ++i)
if(dp[i][lim - 1] < men){
ind = i;
men = dp[i][lim - 1];
}
lim = (1 << n) - 1;
while(ind){
rec.push_back(ind);
int aux = lim;
lim = lim - (1 << (ind - 1));
ind = dad[ind][aux];
}
for(int i = 1; i < giv[rec[rec.size() - 1]].size(); ++i)
ans.push_back(giv[rec[rec.size() - 1]][i]);
for(int i = rec.size() - 2; i >= 0; --i){
int in = giv[rec[i]].size() - tab[rec[i + 1]][rec[i]];
for(int j = in; j < giv[rec[i]].size(); ++j)
ans.push_back(giv[rec[i]][j]);
}
}
void write(){
assert(freopen("adn.out", "w", stdout));
cout << ans;
}
int main(){
read();
solve();
write();
return 0;
}