algorithm
सबसे छोटी सामान्य समस्या

सबसे कम आम सुपरसंकट समस्या मूल जानकारी

सबसे छोटा कॉमन सुपर सीक्वेंस एक समस्या है जो सबसे लंबे समय तक सामान्य अनुवर्तीता से निकटता से संबंधित है, जिसे आप इस कार्य के लिए बाहरी फ़ंक्शन के रूप में उपयोग कर सकते हैं। सबसे छोटी सामान्य सुपर अनुक्रम समस्या एक समस्या है जो सबसे लंबे समय तक सामान्य अनुवर्ती समस्या से निकटता से संबंधित है।

सबसे छोटी सामान्य सुपरसक्वेंस (एससी) न्यूनतम लंबाई का एक सामान्य सुपरसक्वेंस है। कम से कम सामान्य सुपरसक्वेंस समस्या में, दो सीक्वेंस X और Y दिए गए हैं और इन सिक्वेंस का कम से कम कॉमन सुपरसक्वेंस खोजना है। सामान्य तौर पर, एक scs अद्वितीय नहीं है।

दो क्रमों को देखते हुए X = <x1,...,xm> और Y = <y1,...,yn> , एक अनुक्रम U = <u1,...,uk> X और Y का एक सामान्य सुपर अनुक्रम है यदि U , X और Y दोनों का एक सुपर सीक्वेंस है। दूसरे शब्दों में, स्ट्रिंग्स x और y का सबसे छोटा कॉमन सुपर सीक्वेंस एक सबसे छोटा स्ट्रींग z जैसे कि x और y दोनों z बाद के होते हैं।

दो इनपुट अनुक्रमों के लिए, एक स्कैस आसानी से सबसे लंबे समय तक सामान्य (एलसीएस) से बनाई जा सकती है। उदाहरण के लिए, यदि X[1..m]=abcbdab और Y[1..n]=bdcaba , Y[1..n]=bdcaba Z[1..r]=bcba । प्रतीक क्रम को संरक्षित करते हुए गैर-एलसीएस प्रतीकों को डालने से, हमें U[1..t]=abdcabdab मिलता है: U[1..t]=abdcabdab ।

यह बिल्कुल स्पष्ट है कि दो इनपुट अनुक्रमों के लिए r+t=m+n । हालांकि, तीन या अधिक इनपुट अनुक्रमों के लिए यह पकड़ में नहीं आता है। यह भी ध्यान दें, कि lcs और scs समस्याएँ दोहरी समस्याएँ नहीं हैं।

एक स्ट्रिंग को खोजने की अधिक सामान्य समस्या के लिए, S जो स्ट्रिंग्स S1,S2,...,Sl का एक सुपरस्ट्रिंग है, समस्या एनपी-पूर्ण है। इसके अलावा, अच्छे मामले औसत मामले के लिए पाए जा सकते हैं लेकिन सबसे बुरे मामले के लिए नहीं।

सबसे छोटी आम समस्या का उदाहरण:

समय जटिलता: O(max(m,n))

C # में सबसे छोटी सामान्य समस्या का कार्यान्वयन

public class ShortestCommonSupersequence
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }
    
    private static int Lcs(string x, string y, int m, int n)
    {
        var l = new int[m + 1, n + 1];
        for (var i = 0; i <= m; i++)
        {
            for (var j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0) l[i, j] = 0;
                else if (x[i - 1] == y[j - 1]) l[i, j] = l[i - 1, j - 1] + 1;
                else l[i, j] = Max(l[i - 1, j], l[i, j - 1]);
            }
        }
        return l[m, n];
    }

    private static int Scs(string x, string y)
    {
        int m = x.Length, n = y.Length;
        int l = Lcs(x, y, m, n);
        return m + n - l;
    }

    public static int Main(string x, string y)
    {
        return Scs(x, y);
    }
}