Pagini recente » Cod sursa (job #262848) | Cod sursa (job #2457952) | Cod sursa (job #1942503) | Cod sursa (job #764261) | Cod sursa (job #2741307)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
int n, s[(1 << 20)];
string v[20];
string dp[(1 << 20)];
string getNewString(string &a, string &b){
for (int i = 0; i < a.size(); ++i){
bool ok = true;
int j = 0, k = i;
while (j < b.size() && k < b.size()){
if (b[j] != a[k]){
ok = false;
break;
}
++j;
++k;
}
if (ok){
string aux = a;
int idk = n - i;
while (idk < b.size()){
aux += b[idk++];
}
return aux;
}
}
string aux = a;
for (int j = 0; j < b.size(); ++j){
aux += b[j];
}
return aux;
}
int main(){
fin >> n;
for (int i = 1; i <= n; ++i){
fin >> v[i];
dp[(1 << (i - 1))] = v[i];
}
for (int i = 0; i < (1 << n); ++i){
s[i] = (1 << 30);
}
for (int i = 1; i < (1 << n); ++i){
if (dp[i] != ""){
for (int j = 0; j < n; ++j){
if (((i >> j) & 1) == 0){
string aux = getNewString(dp[i], v[j + 1]);
if (aux.size() < s[(i | (1 << j))]){
s[(i | (1 << j))] = aux.size();
dp[(i | (1 << j))] = aux;
}
}
}
}
}
fout << dp[(1 << n) - 1];
fin.close();
fout.close();
return 0;
}