Instantly share code, notes, and snippets.

# yurahuna/aoj2022.cpp Created Oct 24, 2016

 #include 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 Pii; typedef tuple TUPLE; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vp; typedef vector> Graph; const int inf = 1e9; const int mod = 1e9 + 7; int n; vector 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 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 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; } }