algorithm
Il problema più breve di supersequenza comune

Il problema di Supersequenza comune più breve Informazioni di base

La Super Sequenza comune più breve è un problema strettamente correlato alla sottosequenza comune più lunga, che è possibile utilizzare come funzione esterna per questa attività. Il problema più breve comune di super sequenza è un problema strettamente correlato al più lungo problema di sottosuccessione comune.

Una supersequenza (scs) comune più breve è una supersequenza comune di lunghezza minima. Nel problema di supersequenza comune più breve, vengono date le due sequenze X e Y e il compito è trovare una supersequenza comune più breve possibile di queste sequenze. In generale, un SCS non è unico.

Date due sequenze X = <x1,...,xm> e Y = <y1,...,yn> , una sequenza U = <u1,...,uk> è una sequenza super comune di X e Y se U è una super sequenza di X e Y In altre parole, un minor eccellente sequenza comune di stringhe x e y è una breve stringa z tale che sia x ed y sono sottosequenze di z .

Per due sequenze di input, una scs può essere formata facilmente da una sottosequenza (lcs) comune più lunga. Ad esempio, se X[1..m]=abcbdab e Y[1..n]=bdcaba , il lcs è Z[1..r]=bcba . Inserendo i simboli non-lcs preservando l'ordine dei simboli, otteniamo scs: U[1..t]=abdcabdab .

È abbastanza chiaro che r+t=m+n per due sequenze di input. Tuttavia, per tre o più sequenze di input, ciò non vale. Si noti inoltre che i problemi lcs e scs non sono due problemi.

Per il problema più generale di trovare una stringa, S che è una superstringa di un insieme di stringhe S1,S2,...,Sl , il problema è NP-Complete. Inoltre, si possono trovare buone approssimazioni per il caso medio, ma non per il caso peggiore.

Esempio di problema di Supersequenza comune più breve:

Complessità del tempo: O(max(m,n))

Implementazione del problema di Supersequence comune più breve 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);
    }
}