algorithm
Kortaste vanliga övervågsproblem

Kortaste vanliga övervågsproblem Grundläggande information

Den kortaste vanliga supersekvensen är ett problem som är nära relaterat till den längsta vanliga sekvensen, som du kan använda som en extern funktion för den här uppgiften. Det kortaste vanliga supersekvensproblemet är ett problem som är nära relaterat till det längsta vanliga efterföljande problemet.

En kortaste vanliga supersekvens (scs) är en vanlig supersekvens av minimal längd. I det kortaste vanliga supersekvensproblemet ges de två sekvenserna X och Y och uppgiften är att hitta en kortast möjlig gemensam supersekvens för dessa sekvenser. I allmänhet är en scs inte unik.

Givet två sekvenser X = <x1,...,xm> och Y = <y1,...,yn> , är en sekvens U = <u1,...,uk> en vanlig supersekvens av X och Y om U är en supersekvens för både X och Y Med andra ord är den kortaste vanliga supersekvensen för strängarna x och y kortaste strängen z så att både x och y är sekvenser av z .

För två inmatningssekvenser kan en scs enkelt bildas av en längsta vanliga sekvens (lcs). Till exempel, om X[1..m]=abcbdab och Y[1..n]=bdcaba , är lcs Z[1..r]=bcba . Genom att sätta in icke-lcs-symbolerna medan vi U[1..t]=abdcabdab får vi sc: U[1..t]=abdcabdab .

Det är helt tydligt att r+t=m+n för två ingångssekvenser. För tre eller flera ingångssekvenser gäller detta dock inte. Observera också att problemen med lcs och scs inte är dubbla problem.

För det mer allmänna problemet med att hitta en sträng, S som är en superstring av en uppsättning strängar S1,S2,...,Sl , är problemet NP-Complete. Det finns också bra tillnärmningar för det genomsnittliga fallet, men inte i värsta fall.

Exempel på kortaste vanliga supersekvensproblem:

Tidskomplexitet: O(max(m,n))

Implementering av det kortaste vanliga övervågsproblemet i 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);
    }
}