Tìm siêu chuỗi ngắn nhất trong C++

Cho mảng A các chuỗi, tìm chuỗi ngắn nhất chứa mọi chuỗi trong A làm chuỗi con. Giả định không chuỗi nào là chuỗi con của chuỗi khác.

Ví dụ: ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] → "hdsbbhssdbshdbsd".

Giải thuật

1. Tính cost(i,j) = số ký tự cần thêm khi nối chuỗi j sau chuỗi i (tìm overlap lớn nhất).
2. Xây đồ thị cost n x n.
3. DP trên bitmask: dp[mask][j] = độ dài nhỏ nhất của siêu chuỗi chứa các chuỗi trong mask, kết thúc bằng chuỗi j.
4. Khởi tạo dp[1<
5. Chuyển trạng thái: dp[mask][j] = min(dp[prev][k] + cost[k][j]) với prev = mask ^ (1<
6. Truy vết path để xây chuỗi kết quả.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int calc(string& a, string& b){
        for (int i = 0; i < a.size(); i++)
            if (b.find(a.substr(i)) == 0)
                return b.size() - a.size() + i;
        return b.size();
    }
    string shortestSuperstring(vector<string>& A){
        string ret = "";
        int n = A.size();
        vector<vector<int> > graph(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                graph[i][j] = calc(A[i], A[j]);
        vector<vector<int>> dp(1<<n, vector<int>(n, INT_MAX));
        vector<vector<int>> path(1<<n, vector<int>(n, -1));
        int minVal = INT_MAX, last = -1;
        for (int i = 1; i < (1<<n); i++) {
            for (int j = 0; j < n; j++) if (i & (1<<j)) {
                int prev = i ^ (1<<j);
                if (prev == 0) dp[i][j] = A[j].size();
                else for (int k = 0; k < n; k++)
                    if ((prev & (1<<k)) && dp[prev][k] != INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
                        dp[i][j] = dp[prev][k] + graph[k][j];
                        path[i][j] = k;
                    }
                if (i == (1<<n)-1 && dp[i][j] < minVal) { minVal = dp[i][j]; last = j; }
            }
        }
        int curr = (1<<n) - 1;
        stack<int> st;
        while (curr > 0) { st.push(last); int temp = curr; curr -= (1<<last); last = path[temp][last]; }
        int i = st.top(); st.pop(); ret += A[i];
        while (!st.empty()) { int j = st.top(); st.pop(); ret += A[j].substr(A[j].size() - graph[i][j]); i = j; }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
    cout << (ob.shortestSuperstring(v));
}

Đầu vào

{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}

Đầu ra

hdsbbhssdbshdbsd