algorithm
Kürzestes häufiges Problem der Supersequenz

Kürzeste häufige Supersequenzproblematik Grundlegende Informationen

Die kürzeste gemeinsame Supersequenz ist ein Problem, das eng mit der längsten gemeinsamen Untersequenz zusammenhängt, die Sie als externe Funktion für diese Aufgabe verwenden können. Das kürzeste häufige Supersequenzproblem ist ein Problem, das eng mit dem am längsten auftretenden Subsequenzproblem zusammenhängt.

Eine kürzeste häufige Supersequenz (scs) ist eine häufige Supersequenz minimaler Länge. Bei dem kürzesten gemeinsamen Supersequenzproblem sind die zwei Sequenzen X und Y gegeben und die Aufgabe besteht darin, eine möglichst kurze gemeinsame Supersequenz dieser Sequenzen zu finden. Im Allgemeinen ist ein SCS nicht eindeutig.

Wenn zwei Sequenzen X = <x1,...,xm> und Y = <y1,...,yn> , ist eine Sequenz U = <u1,...,uk> eine übliche Supersequenz von X und Y if U ist eine Supersequenz von X und Y Mit anderen Worten ist eine kürzeste gemeinsame Superfolge von Zeichenketten x und y eine kürzeste Zeichenfolge z so dass sowohl x als auch y Untersequenzen von z .

Für zwei Eingabesequenzen kann ein scs leicht aus einer längsten gemeinsamen Untersequenz (lcs) gebildet werden. Wenn zum Beispiel X[1..m]=abcbdab und Y[1..n]=bdcaba , ist die lcs Z[1..r]=bcba . Durch Einfügen der Nicht-lcs-Symbole unter Beibehaltung der Symbolreihenfolge erhalten wir die scs: U[1..t]=abdcabdab .

Es ist ziemlich klar, dass r+t=m+n für zwei Eingangssequenzen ist. Für drei oder mehr Eingabesequenzen gilt dies jedoch nicht. Beachten Sie auch, dass die Lcs- und Scs-Probleme keine dualen Probleme sind.

Für das allgemeinere Problem des Findens einer Zeichenkette, S die eine Superzeichenfolge aus einem Satz von Zeichenfolgen S1,S2,...,Sl , ist das Problem NP-Complete. Auch für den Durchschnittsfall lassen sich gute Näherungen finden, für den Worst-Case jedoch nicht.

Beispiel für das kürzeste häufige Problem der Supersequenz:

Zeitkomplexität: O(max(m,n))

Implementierung des kürzesten gemeinsamen Supersequenzproblems 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);
    }
}