Pagini recente » Cod sursa (job #2657433) | Cod sursa (job #3249618) | Cod sursa (job #255884) | Cod sursa (job #1960536) | Cod sursa (job #2961576)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
void build_lps(string word, vector<int> &lps){
int len = 0, i = 1;
int m = word.size();
lps.resize(m);
while(i < m){
if(word[i] == word[len]){
lps[i++] = ++len;
}
else{
if(len){
len = lps[len - 1];
}
else{
lps[i++] = 0;
}
}
}
}
int get_overlap(string prefix, string suffix){
int i = 0, j = 0, l = 0;
int m = suffix.size();
int n = prefix.size();
vector<int> lps(2000005);
build_lps(suffix, lps);
while(i < n){
if(prefix[i] == suffix[j]){
++i;
++j;
}
if(j == m){
break;
++l;
j = lps[j - 1];
}
else if(i < n && prefix[i] != suffix[j]){
if(j != 0){
j = lps[j - 1];
}
else ++i;
}
}
return j;
}
int main()
{
int n;
fin >> n;
vector<string> words1(n);
for (auto &it:words1) {
fin >> it;
}
vector<bool> overlapped(n, false);
vector<vector<int> > cost1(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j || overlapped[i] || overlapped[j]) {
continue;
}
cost1[i][j] = get_overlap(words1[i], words1[j]);
if (cost1[i][j] == words1[j].size()) {
overlapped[j] = true;
}
}
}
vector<string> words;
for (int i = 0; i < n; ++i) {
if (!overlapped[i]) {
words.push_back(words1[i]);
}
}
n = words.size();
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) {
continue;
}
cost[i][j] = get_overlap(words[i], words[j]);
}
}
vector<vector<int> > dp(n, vector<int>(1 << n, INT_MAX));
vector<vector<int> > past(n, vector<int>(1 << n, -1));
for (int i = 0; i < n; ++i) {
dp[i][1 << i] = words[i].size();
}
for (int mask = 1; mask < (1 << n); ++mask) {
for (int i = 0; i < n; ++i) {
if ((mask | (1 << i)) != mask) {
continue;
}
if (dp[i][mask] == INT_MAX) {
continue;
}
for (int j = 0; j < n; ++j) {
if ((mask | (1 << j)) == mask) {
continue;
}
int newcost = dp[i][mask] + int(words[j].size()) - cost[i][j];
if (dp[j][mask | (1 << j)] > newcost) {
past[j][mask | (1 << j)] = i;
dp[j][mask | (1 << j)] = newcost;
}
}
}
}
int sol = INT_MAX;
int word = -1, mask = (1 << n) - 1;
for (int i = 0; i < n; ++i) {
if (dp[i][(1 << n) - 1] < sol) {
sol = dp[i][(1 << n) - 1];
word = i;
}
}
stack<char> stk;
for (int i = words[word].size() - 1; i >= 0; --i) {
stk.push(words[word][i]);
}
for (int i = 1; i < n; ++i) {
int nxt = past[word][mask];
for (int j = words[nxt].size() - 1 - cost[nxt][word]; j >= 0; --j) {
stk.push(words[nxt][j]);
}
mask ^= (1 << word);
word = nxt;
}
while(!stk.empty()) {
fout << stk.top();
stk.pop();
}
return 0;
}