943-1

class Solution {
    inline static char dp[1 << 12][12];
    inline static char parent[1 << 12][12];
    inline static char olap[12][12];
    inline static char pre[42];
    int overlap(const string& s1, const string& s2) {
        auto s = s2 + "_" + s1;
        int N = s.length();
        memset(pre, 0, sizeof(pre));
        for (int i = 0, j = 1; j < N;) {
            if (s[i] == s[j])
                pre[++j] = ++i;
            else if (i)
                i = pre[i];
            else
                ++j;
        }
        return pre[N];
    }
public:
    string shortestSuperstring(vector<string>& words) {
        int N = words.size();
        memset(dp, 0, sizeof(dp));
        memset(parent, -1, sizeof(parent));
        memset(olap, 0, sizeof(olap));
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                olap[i][j] = overlap(words[i], words[j]);

        for (int i = 1; i < 1 << N; ++i) {
            for (int j = 0; j < N; ++j) {
                int next = i | 1 << j;
                if (next == i)
                    continue;
                for (int k = 0; k < N; ++k) {
                    if (!(i & 1 << k))
                        continue;
                    int o = dp[i][k] + olap[k][j];
                    if (o >= dp[next][j]) {
                        dp[next][j] = o;
                        parent[next][j] = k;
                    }
                }
            }
        }

        int best = 0;
        int cur = -1;
        for (int j = 0; j < N; ++j)
            if (dp[(1 << N) - 1][j] >= best) {
                cur = j;
                best = dp[(1 << N) - 1][j];
            }
        stack<int> path;
        for (int mask = (1 << N) - 1, prev; cur != -1; ) {
            path.emplace(cur);
            prev = parent[mask][cur];
            mask &= ~(1 << cur);
            cur = prev;
        }
        string result;
        for (int prev = -1, next; !path.empty(); prev = next) {
            next = path.top(), path.pop();
            result += words[next].substr(prev == -1 ? 0 : olap[prev][next]);
        }
        return result;
    }
};