algorithm
El problema más corto de la supersecuencia

Información básica sobre el problema de la supersecuencia más corta

La súper secuencia más corta es un problema estrechamente relacionado con la subsecuencia común más larga, que puede utilizar como una función externa para esta tarea. El problema de súper secuencia común más corto es un problema estrechamente relacionado con el problema de subsecuencia común más largo.

Una supersecuencia más corta (scs) es una supersecuencia común de longitud mínima. En el problema más corto de supersecuencia común, se dan las dos secuencias X e Y , y la tarea es encontrar una súper secuencia común lo más corta posible de estas secuencias. En general, un scs no es único.

Dadas dos secuencias X = <x1,...,xm> e Y = <y1,...,yn> , una secuencia U = <u1,...,uk> es una super secuencia común de X e Y si U es una super secuencia de X e Y En otras palabras, una secuencia de súper común más corto de cadenas x y y es una cadena más corta z de tal manera que ambos x y y son subsecuencias de z .

Para dos secuencias de entrada, un scs puede formarse a partir de una subsecuencia común más larga (lcs) fácilmente. Por ejemplo, si X[1..m]=abcbdab e Y[1..n]=bdcaba , el lcs es Z[1..r]=bcba . Al insertar los símbolos no-lcs mientras se conserva el orden de los símbolos, obtenemos los scs: U[1..t]=abdcabdab .

Es bastante claro que r+t=m+n para dos secuencias de entrada. Sin embargo, para tres o más secuencias de entrada esto no es válido. Tenga en cuenta también que los problemas de lcs y scs no son problemas duales.

Para el problema más general de encontrar una cadena, S , que es una supercadena de un conjunto de cadenas S1,S2,...,Sl , el problema es NP-Completo. Además, se pueden encontrar buenas aproximaciones para el caso promedio pero no para el peor de los casos.

Ejemplo de problema de supersecuencia más corto:

Complejidad de tiempo: O(max(m,n))

Implementación del problema más corto de supersecuencia en 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);
    }
}