algorithm
Kortste vaak voorkomende probleem van supersequentie

Kortste Common Supersequence Probleem Basisinformatie

De kortste gemeenschappelijke superreeks is een probleem dat nauw verband houdt met de langste gemeenschappelijke deelreeks, die u als externe functie voor deze taak kunt gebruiken. Het kortste veel voorkomende probleem met de supersequentie is een probleem dat nauw verband houdt met het langste gemeenschappelijke deelprobleem.

Een kortste algemene supersequentie (scs) is een algemene supersequentie van minimale lengte. In het kortste algemene probleem van de supersequentie worden de twee reeksen X en Y gegeven en de taak is om een zo kort mogelijke algemene supersequentie van deze reeksen te vinden. Over het algemeen is een scs niet uniek.

Gegeven twee reeksen X = <x1,...,xm> en Y = <y1,...,yn> , is een reeks U = <u1,...,uk> een veel voorkomende superreeks van X en Y als U is een superreeks van zowel X als Y Met andere woorden, een kortste gemeenschappelijke superreeks van reeksen x en y is een kortste reeks z zodat zowel x als y deelreeksen van z .

Voor twee invoerreeksen kan een scs gemakkelijk worden gevormd uit een langste gemeenschappelijke deelreeks (lcs). Als bijvoorbeeld X[1..m]=abcbdab en Y[1..n]=bdcaba , is de lcs Z[1..r]=bcba . Door de niet-lcs-symbolen in te voegen met behoud van de symboolvolgorde, krijgen we de scs: U[1..t]=abdcabdab .

Het is vrij duidelijk dat r+t=m+n voor twee invoerreeksen. Voor drie of meer invoerreeksen geldt dit echter niet. Merk ook op dat de lcs en de scs-problemen geen dubbele problemen zijn.

Voor het meer algemene probleem van het vinden van een string, S die een superstring is van een reeks strings S1,S2,...,Sl , is het probleem NP-Complete. Ook kunnen goede schattingen worden gevonden voor het gemiddelde geval, maar niet voor het slechtste geval.

Voorbeeld van kortste veel voorkomende probleem van supersequentie:

Tijdcomplexiteit: O(max(m,n))

Implementatie van kortste veelvoorkomende supersequentieprobleem in 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);
    }
}