algorithm
Najkrótszy wspólny problem nadsekwencji

Najkrótszy wspólny problem supersekwencji Podstawowe informacje

Najkrótsza wspólna supersekwencja jest problemem ściśle związanym z najdłuższym wspólnym podsekwencją, którego można użyć jako funkcji zewnętrznej dla tego zadania. Najkrótszy wspólny problem supersekwencji jest problemem ściśle związanym z najdłuższym wspólnym problemem podsekwencji.

Najkrótsza wspólna supersekwencja (scs) to powszechna supersekwencja o minimalnej długości. W najkrótszym wspólnym problemie supersekwencji podane są dwie sekwencje X i Y a zadaniem jest znalezienie najkrótszej możliwej wspólnej supersekwencji tych sekwencji. Ogólnie rzecz biorąc, SCS nie jest unikalny.

Biorąc pod uwagę dwie sekwencje X = <x1,...,xm> i Y = <y1,...,yn> , sekwencja U = <u1,...,uk> jest wspólną supersekwencją X i Y jeśli U jest super sekwencją zarówno X jak i Y Innymi słowy, najkrótsza wspólna supersekwencja ciągów x i y jest najkrótszym ciągiem z tak że zarówno x jak i y są podsekwencjami z .

W przypadku dwóch sekwencji wejściowych można łatwo utworzyć scs z najdłuższej wspólnej podsekwencji (lcs). Na przykład, jeśli X[1..m]=abcbdab i Y[1..n]=bdcaba , lcs to Z[1..r]=bcba . Wstawiając symbole inne niż lcs przy zachowaniu kolejności symboli, otrzymujemy scs: U[1..t]=abdcabdab .

Jest całkiem jasne, że r+t=m+n dla dwóch sekwencji wejściowych. Jednak w przypadku trzech lub więcej sekwencji wejściowych nie ma to zastosowania. Zauważ też, że problemy lcs i scs nie są podwójnymi problemami.

Dla bardziej ogólnego problemu znalezienia łańcucha, S który jest superstrunem zestawu łańcuchów S1,S2,...,Sl , problemem jest NP-Complete. Również dobre przybliżenia można znaleźć dla przeciętnego przypadku, ale nie dla najgorszego.

Przykład najkrótszego typowego problemu nadsekwencji:

Złożoność czasu: O(max(m,n))

Implementacja najkrótszego wspólnego problemu supersekwencji w 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);
    }
}