Cod sursa(job #2961577)

Utilizator CharacterMeCharacter Me CharacterMe Data 6 ianuarie 2023 18:45:22
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.88 kb
#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, vector<int> lps){

    int i = 0, j = 0, l = 0;
    int m = suffix.size();
    int n = prefix.size();

    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<vector<int> > lps1(n);
    for (int i = 0; i < n; ++i) {
        build_lps(words1[i], lps1[i]);
    }

    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], lps1[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> > lps(n);
    for (int i = 0; i < n; ++i) {
        build_lps(words[i], lps[i]);
    }

    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], lps[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;
}