Code : Compress Strings

#include <bits/stdc++.h>
using namespace std;

const int inf = 2 * (int)1e5 + 1;

class Graph {
  public:
    int n;
    vector<vector<int>> d;
    vector<int> node_cost;

    Graph(int n) {
        this->n = n;
        d.resize(n, vector<int>(n, inf));
        node_cost.resize(n);
    }

    // Minimum weight Hamiltonian path.
    int tsp() {
        int full_mask = (1 << n) - 1;
        vector<vector<int>> dp(n, vector<int>(full_mask + 1, inf));

        for (int i = 0; i < n; i++) {
            dp[i][1 << i] = node_cost[i];
        }

        for (int cnt = 0; cnt <= n; cnt++) {
            for (int mask = 0; mask <= full_mask; mask++) {
                if (__builtin_popcount(mask) != cnt) {
                    continue;
                }

                for (int i = 0; i < n; i++) {
                    if (((1 << i) & mask) == 0) {
                        continue;
                    }
                    for (int j = 0; j < n; j++) {
                        if ((1 << j) & mask) {
                            continue;
                        }
                        int nxt = mask | (1 << j);
                        dp[j][nxt] = min(dp[j][nxt], dp[i][mask] + d[i][j]);
                    }
                }
            }
        }

        int ans = inf;
        for (int i = 0; i < n; i++) {
            ans = min(ans, dp[i][full_mask]);
        }
        return ans;
    }
};

bool is_substring(string &big, string &small) {
    return big.find(small) != string::npos;
}

// How many extra characters do you need to append to left so that right
// appears as a suffix?
int merge_cost(string &left, string &right) {
    for (int i = 0; i < left.size(); i++) {
        string suffix = left.substr(i);
        if (right.substr(0, suffix.length()) == suffix) {
            return right.length() - suffix.length();
        }
    }
    return right.length();
}

void solve() {
    int n;
    cin >> n;

    vector<string> store(n);
    for (int i = 0; i < n; i++) {
        cin >> store[i];
    }

    for (auto itr = store.begin(); itr != store.end();) {
        bool is_embedded = false;
        for (auto jtr = store.begin(); jtr != store.end(); jtr++) {
            if (itr != jtr && is_substring(*jtr, *itr)) {
                is_embedded = true;
            }
        }
        if (is_embedded) {
            itr = store.erase(itr);
        } else {
            itr++;
        }
    }

    n = store.size();
    Graph g(n);
    for (int i = 0; i < n; i++) {
        g.node_cost[i] = store[i].length();
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            g.d[i][j] = merge_cost(store[i], store[j]);
        }
    }

    cout << g.tsp() << endl;
}

int main() {
    solve();
    return 0;
}

#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int inf = 2 * (int)1e5 + 1;

class Graph {
  public:
    int n;
    vector<vector<int>> d;
    vector<int> node_cost;

    Graph(int n) {
        this->n = n;
        d.resize(n, vector<int>(n, inf));
        node_cost.resize(n);
    }

    // Minimum weight Hamiltonian path.
    int tsp() {
        int full_mask = (1 << n) - 1;
        vector<vector<int>> dp(n, vector<int>(full_mask + 1, inf));

        for (int i = 0; i < n; i++) {
            dp[i][1 << i] = node_cost[i];
        }

        for (int cnt = 0; cnt <= n; cnt++) {
            for (int mask = 0; mask <= full_mask; mask++) {
                if (__builtin_popcount(mask) != cnt) {
                    continue;
                }

                for (int i = 0; i < n; i++) {
                    if (((1 << i) & mask) == 0) {
                        continue;
                    }
                    for (int j = 0; j < n; j++) {
                        if ((1 << j) & mask) {
                            continue;
                        }
                        int nxt = mask | (1 << j);
                        dp[j][nxt] = min(dp[j][nxt], dp[i][mask] + d[i][j]);
                    }
                }
            }
        }

        int ans = inf;
        for (int i = 0; i < n; i++) {
            ans = min(ans, dp[i][full_mask]);
        }
        return ans;
    }
};

vector<int> prefix_function(string &s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

bool is_substring(string &big, string &small) {
    string combo = small + "$" + big;
    vector<int> pi = prefix_function(combo);
    for (int i = 0; i < (int)pi.size(); i++) {
        if (pi[i] == small.length()) {
            return true;
        }
    }
    return false;
}

// How many extra characters do you need to append to left so that right
// appears as a suffix?
int merge_cost(string &left, string &right) {
    string combo = right + "$" + left;
    vector<int> pi = prefix_function(combo);
    return (int)right.size() - pi.back();
}

void solve() {
    int n;
    cin >> n;

    vector<string> store(n);
    for (int i = 0; i < n; i++) {
        cin >> store[i];
    }

    for (auto itr = store.begin(); itr != store.end();) {
        bool is_embedded = false;
        for (auto jtr = store.begin(); jtr != store.end(); jtr++) {
            if (itr != jtr && is_substring(*jtr, *itr)) {
                is_embedded = true;
            }
        }
        if (is_embedded) {
            itr = store.erase(itr);
        } else {
            itr++;
        }
    }

    n = store.size();
    Graph g(n);
    for (int i = 0; i < n; i++) {
        g.node_cost[i] = store[i].length();
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            g.d[i][j] = merge_cost(store[i], store[j]);
        }
    }

    cout << g.tsp() << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}