Pagini recente » Cod sursa (job #2108196) | Cod sursa (job #2085455) | Cod sursa (job #1731072) | Cod sursa (job #1285852) | Cod sursa (job #2801020)
#include <bits/stdc++.h>
using namespace std;
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
using vva = vector <vector <array <int, 2>>>;
using vv = vector <vector <int>>;
using v = vector <string>;
void printSTR(v vec, vv ccc, vva path, array <int, 2> cur) {
if(cur[0] == 0)
return;
printSTR(vec, ccc, path, path[cur[0]][cur[1]]);
int cost = ccc[path[cur[0]][cur[1]][1]][cur[1]];
if(path[cur[0]][cur[1]][0] == 0)
cost = 0;
cout << vec[cur[1]].substr(cost);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
const int INF = 1e9;
auto KMP = [](string str1, string str2) {
str1 = ' ' + str1;
str2 = ' ' + str2;
int len = str1.size() - 1, lenn = str2.size() - 1, q = 0;
vector <int> pi(len + 1);
for(int i = 2;i <= len;i++) {
while(q && str1[q + 1] != str1[i])
q = pi[q];
if(str1[q + 1] == str1[i])
q++;
pi[i] = q;
}
q = 0;
for(int i = 1;i <= lenn;i++) {
while(q && str1[q + 1] != str2[i])
q = pi[q];
if(str1[q + 1] == str2[i])
q++;
if(q == len)
return 1;
}
return 0;
};
auto LenPS = [](string str1, string str2) {
string str = "2" + str2 + "2" + str1;
int len = str.size(), q = 0;
vector <int> pi(len);
//pi[1] = 0;
for(int i = 2;i < len;i++) {
while(q && str[q + 1] != str[i])
q = pi[q];
if(str[q + 1] == str[i])
q++;
pi[i] = q;
}
return pi.back();
};
auto cmp = [](string str1, string str2) {
return str1.size() < str2.size();
};
Open("adn");
int N; cin >> N;
vector <string> v(N);
for(string &x : v)
cin >> x;
sort(v.begin(), v.end(), cmp);
vector <bool> marked(N);
for(int i = 0;i < N - 1;i++)
for(int j = i + 1;j < N;j++)
if(KMP(v[i], v[j]) == 1) {
marked[i] = 1;
break;
}
for(int i = 0, cnt = 0;i < N;i++) {
if(marked[i]) {
v.erase(v.begin() + i - cnt);
cnt++;
}
}
N = v.size();
vector <vector <array <int, 2>>> Gr(N);
vector <vector <int>> cost(N, vector <int>(N));
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
if(i != j) {
int val = LenPS(v[i], v[j]);
Gr[j].push_back({i, val});
cost[i][j] = val;
}
int limit = 1 << N;
vector <vector <int>> dp(limit, vector <int>(N, -INF));
vector <vector <array <int, 2>>> path(limit, vector <array <int, 2>>(N));
for(int i = 0;i < N;i++)
dp[1 << i][i] = 0;
for(int i = 0;i < limit;i++)
for(int j = 0;j < limit;j++) {
if((i & (1 << j)) == 0)
continue;
for(array <int, 2> it : Gr[j]) {
if((i & (1 << it[0])) == 0)
continue;
if(dp[i ^ (1 << j)][it[0]] + it[1] > dp[i][j]) {
dp[i][j] = dp[i ^ (1 << j)][it[0]] + it[1];
path[i][j] = {i ^ (1 << j), it[0]};
}
}
}
int ans = -INF;
array <int, 2> ppp;
for(int i = 0;i < N;i++){
if(dp[limit - 1][i] > ans) {
ans = dp[limit - 1][i];
ppp = {limit - 1, i};
}
}
printSTR(v, cost, path, ppp);
return 0;
}