Pagini recente » Cod sursa (job #1027602) | Cod sursa (job #3163033) | Cod sursa (job #2136531) | Cod sursa (job #2937036) | Cod sursa (job #2962624)
#include<fstream>
#include <vector>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
vector <string> v;
int N, prefixes[20][30010], rest_add[20][20];
int dp[20][1 << 20], sol[20][1 << 20], order[20];
void kmp(int i){
int common = 0;
prefixes[i][1] = 0;
for(int j = 2; j <= v[i].size(); j++){
while(common != 0 && v[i][common + 1] != v[i][j])
common = prefixes[i][common];
if(v[i][common + 1] == v[i][j])
common++;
prefixes[i][j] = common;
}
}
int compute(int i, int j){
int aux = 0;
for(int it = 1; it < v[i].size() ; it++){
while(aux > 0 && v[j][aux + 1] != v[i][it])
aux = prefixes[j][aux];
if(v[j][aux + 1] == v[i][it])
aux++;
if(aux + 1 == v[j].size())
return 1e9;
}
return v[j].size() - aux - 1;
}
int main(){
fin >> N;
for(int i = 1; i <= N; i++){
string s; fin >> s;
s = ' ' + s;
v.push_back(s);
}
for(int i = 0; i < N; i++)
kmp(i);
for(int i = 0; i < N; i++) {
for(int j = 0; j < (1 << N); j++)
dp[i][j] = 1e9;
dp[i][1 << i] = v[i].size() - 1;
}
int mask = (1 << N) - 1, nr = N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j && (mask & (1 << j))){
rest_add[i][j] = compute(i, j);
if(rest_add[i][j] == 1e9){
mask ^= (1 << j);
nr--;
}
}
for(int i = 1; i <= mask; i++)
for(int j = 0; j < N; j++)
if((i & (1 << j)) && (mask & (1 << j)))
for(int it = 0; it < N; it++)
if(!(i & (1 << it)) && (mask & (1 << it)) && dp[it][i ^ (1 << it)] > dp[j][i] + rest_add[j][it]){
dp[it][i ^ (1 << it)] = dp[j][i] + rest_add[j][it];
sol[it][i ^ (1 << it)] = j;
}
int mini = 1e9, pos = 0;
int poz = nr, crt = mask;
for(int i = 0; i < N; i++)
if((mask & (1 << i)) && dp[i][mask] < mini){
mini = dp[i][mask];
pos = i;
}
order[poz--] = pos;
for(int i = 2; i <= nr; i++){
int aux = pos;
pos = sol[pos][crt];
crt ^= (1 << aux);
order[poz--] = pos;
}
for(int i = 0; i < N; i++)
v[i].erase(v[i].begin());
fout << v[order[1]];
for(int i = 2 ; i <= nr; i++){
for(int j = v[order[i]].size() - rest_add[order[i - 1]][order[i]]; j < v[order[i]].size(); j++)
fout << v[order[i]][j];
}
return 0;
}