Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सबसे छोटा सुपरस्ट्रिंग ढूंढें C++ में

मान लीजिए हमारे पास स्ट्रिंग्स की एक सरणी A है, हमें कोई भी सबसे छोटी स्ट्रिंग ढूंढनी है जो A में प्रत्येक स्ट्रिंग को सबस्ट्रिंग के रूप में समाहित करती है। हम यह भी मान सकते हैं कि A में कोई भी स्ट्रिंग A की किसी अन्य स्ट्रिंग का सबस्ट्रिंग नहीं है।

उदाहरण के लिए, यदि इनपुट ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] है, तो आउटपुट "hdsbbhssdbshdbsd" होगा।

हल करने का दृष्टिकोण

यह यात्रा विक्रेता समस्या (TSP) का एक रूपांतर है जिसमें DP और बिटमास्क का उपयोग होता है:

  • calc(a, b) = b को a के बाद जोड़ने पर अतिरिक्त लंबाई की गणना करें

  • सभी जोड़ियों के लिए ओवरलैप ग्राफ बनाएं

  • dp[mask][i] = मास्क द्वारा दर्शाए गए स्ट्रिंग्स को कवर करने वाली न्यूनतम लंबाई जो i पर समाप्त होती है

  • पथ पुनर्निर्माण के लिए पथ सरणी का उपयोग करें

  • सभी मास्क और अंतिम नोड्स पर पुनरावृति करें

  • इष्टतम पथ से सुपरस्ट्रिंग पुनर्निर्मित करें

उदाहरण

#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 (int)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]); 
                graph[j][i] = calc(A[j], A[i]); 
            } 
        } 
        
        int dp[1 << n][n]; 
        int path[1 << n][n]; 
        int minVal = INT_MAX; 
        int last = -1; 
        
        for (int i = 0; i < (1 << n); i++) 
            for (int j = 0; j < n; j++) 
                dp[i][j] = INT_MAX; 
        
        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)); 
    return 0;
}

इनपुट

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

आउटपुट

hdsbbhssdbshdbsd
  1. C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम

    इस समस्या में, हमें दो बिंदु A और B दिए गए हैं, एक रेखा के प्रारंभिक और अंतिम बिंदु। हमारा कार्य C++ में रेखा का मध्य बिंदु खोजने के लिए एक प्रोग्राम बनाना है। समस्या विवरण यहां, हमारे पास प्रारंभिक और अंतिम बिंदु A(x1, y1) और B(x2, y2) वाली एक रेखा है। और हमें रेखा का मध्य बिंदु ज्ञात करना है। उद

  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ