C++ Bottom up DP + KMP 20ms
\nclass Solution {\n    static int dp[4096][12];\n    static int failure[12][20];\n    static int cost[12][12];\n    static int trace_table[4096][12];\n    \npu
```\nclass Solution {\n    static int dp[4096][12];\n    static int failure[12][20];\n    static int cost[12][12];\n    static int trace_table[4096][12];\n    \npublic:\n    string shortestSuperstring(vector<string>& A) {\n        const int sz = A.size();\n        const int dp_sz = 1 << sz;\n        \n        std::fill(&dp[0][0], std::next(&dp[0][0], sizeof(dp)), 0);\n        \n        // compute the failure table for each string\n        for (int i = 0; i < sz; i++) {\n            const int str_sz = A[i].size();\n            \n            failure[i][0] = -1;\n            \n            for (int j = 1, k = -1; j < str_sz; j++) {\n                while (k >= 0 && A[i][k + 1] != A[i][j])\n                    k = failure[i][k];\n                \n                if (A[i][k + 1] == A[i][j]) k++;\n                \n                failure[i][j] = k;\n            }\n        }\n        \n        // compute the append cost\n        for (int i = 0; i < sz; i++) {\n            const int i_sz = A[i].size();\n            \n            for (int j = 0; j < sz; j++) {\n                if (i != j) {\n                    const int j_sz = A[j].size();\n                    int h = -1;\n                \n                    for (int k = 0; k < j_sz; k++) {\n                        while (h >= 0 && A[i][h + 1] != A[j][k])\n                            h = failure[i][h];\n                        \n                        if (A[i][h + 1] == A[j][k])\n                            h++;\n                    }\n                    \n                    cost[j][i] = i_sz - h - 1;\n                }\n            }\n        }\n        \n        // process bottom-up DP\n        for (int i = 0; i < sz; i++)\n            dp[1 << i][i] = A[i].size();\n        \n        for (int state = 1; state < dp_sz; state++) {\n            for (int t1 = state, b1 = t1 & (-t1); t1 ; t1 ^= b1 , b1 = t1 & (-t1)) {\n                const int state1 = state ^ b1;\n                const int i = __builtin_ctz(b1);\n                const int i_sz = A[i].size();\n                \n                for (int t2 = state1, b2 = t2 & (-t2); t2; t2 ^= b2, b2 = t2 & (-t2)) {    \n                    const int j = __builtin_ctz(b2);\n                    const int tmp = dp[state1][j] + cost[j][i];\n                    \n                    if (!dp[state][i] || tmp < dp[state][i]) {\n                        dp[state][i] = tmp;\n                        trace_table[state][i] = j;\n                    }\n                }\n            }\n        }\n        \n        const auto last = dp[dp_sz - 1];\n        string res;\n        \n        int i = std::distance(last, std::min_element(last, last + sz));\n        \n        for (int state = dp_sz - 1, j = trace_table[state][i]; state & (state - 1); state ^= (1 << i), i = j, j = trace_table[state][i])\n            res = A[i].substr(A[i].size() - cost[j][i]) + res;\n        \n        return A[i] + res;\n    }\n};\n\nint Solution::dp[4096][12];\nint Solution::failure[12][20];\nint Solution::cost[12][12];\nint Solution::trace_table[4096][12];\n```
[]