algorithm
Problème de supersquence commun le plus court

Problème de supersquence commune le plus court

La séquence la plus courte commune est un problème étroitement lié à la plus longue sous-séquence commune, que vous pouvez utiliser comme fonction externe pour cette tâche. Le problème de la super séquence commune le plus court est un problème étroitement lié au plus long problème de sous-séquence commun.

Une supersquence commune la plus courte (scs) est une supersquence commune de longueur minimale. Dans le plus court problème de supersquence commun, les deux séquences X et Y sont données et la tâche est de trouver une supersquence commune la plus courte possible de ces séquences. En général, un scs n'est pas unique.

Étant donné deux séquences X = <x1,...,xm> et Y = <y1,...,yn> , une séquence U = <u1,...,uk> est une super séquence commune de X et Y si U est une super séquence de X et Y En d'autres termes, une super-séquence commune la plus courte de chaînes x et y est la chaîne la plus courte z telle que x et y soient des sous-séquences de z .

Pour deux séquences d'entrée, un scs peut être formé à partir d'une plus longue sous-séquence commune (lcs) facilement. Par exemple, si X[1..m]=abcbdab et Y[1..n]=bdcaba , le lcs est Z[1..r]=bcba . En insérant les symboles non-lcs tout en préservant l'ordre des symboles, on obtient les scs: U[1..t]=abdcabdab .

Il est clair que r+t=m+n pour deux séquences d'entrée. Cependant, pour trois séquences d'entrée ou plus, cela ne tient pas. Notez également que les problèmes lcs et scs ne sont pas des problèmes doubles.

Pour le problème plus général de trouver une chaîne, S qui est une superstring d'un ensemble de chaînes S1,S2,...,Sl , le problème est NP-Complete. En outre, de bonnes approximations peuvent être trouvées pour le cas moyen mais pas pour le pire des cas.

Exemple de problème de supersquence commun le plus court:

Complexité temporelle: O(max(m,n))

Implémentation du plus court problème de supersquence commune 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);
    }
}