Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <bits/stdc++.h>
using namespace std;
#define int long long // <-----!!!!!!!!!!!!!!!!!!!
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;
int n;
vector<string> s;
vvi d;
vvi dp;
int common(string s, string t) {
for (int k = min(s.size(), t.size()); k >= 0; k--) {
if (s.substr((int)s.size() - k) == t.substr(0, k)) {
return k;
}
}
}
string concat(string s, string t) {
int k = common(s, t);
return s + t.substr(k);
}
string mymin(string s, string t) {
if (s.size() < t.size()) return s;
if (s.size() > t.size()) return t;
return s < t ? s : t;
}
string dfs(int state, int j, string str) {
if (__builtin_popcount(state) == 1) return concat(s[j], str);
string ret(101, 'z');
rep(i, n) {
if (!((state >> i) & 1)) continue;
if (dp[state - (1 << j)][i] + d[i][j] == dp[state][j]) {
ret = mymin(ret, dfs(state - (1 << j), i, concat(s[i], str)));
}
}
return ret;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t = 0;
while (cin >> n, n) {
s.clear();
s.resize(n);
rep(i, n) cin >> s[i];
vector<bool> alive(n, true);
rep(i, n) {
rep2(j, i + 1, n) {
if (s[i] == s[j]) {
alive[j] = false;
}
}
}
rep(i, n) {
rep(j, n) {
if (i == j) continue;
if (s[i] != s[j] && s[i].find(s[j]) != string::npos) {
alive[j] = false;
}
}
}
{
vector<string> t;
rep(i, n) {
if (alive[i]) {
t.emplace_back(s[i]);
}
}
s = t;
n = s.size();
}
d.clear();
d.resize(n, vi(n));
rep(i, n) {
rep(j, n) {
if (i == j) continue;
d[i][j] = common(s[i], s[j]);
}
}
dp.clear();
dp.resize(1 << n, vi(n, -1));
rep(i, n) {
dp[1 << i][i] = 0;
}
rep(state, 1 << n) {
rep(i, n) {
if (dp[state][i] == -1) continue;
rep(j, n) {
if ((state >> j) & 1) continue;
dp[state | (1 << j)][j] = max(dp[state | (1 << j)][j], dp[state][i] + d[i][j]);
}
}
}
int mx = *max_element(all(dp[(1 << n) - 1]));
string ans(101, 'z');
rep(j, n) {
if (dp[(1 << n) - 1][j] == mx) {
ans = mymin(ans, dfs((1 << n) - 1, j, s[j]));
}
}
cout << ans << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment