algorithm
Кратчайшая общая проблема суперсимметрии

Кратчайшая общая проблема суперсимметрии Основная информация

Самая короткая общая суперпоследовательность - проблема, тесно связанная с самой длинной общей подпоследовательью, которую вы можете использовать в качестве внешней функции для этой задачи. Кратчайшая общая проблема суперпоследовательности - проблема, тесно связанная с самой длинной общей проблемой подпоследовательности.

Кратчайшая общая суперсимметрия (scs) является общей суперсимметрией минимальной длины. В кратчайшей общей проблеме суперсимментации заданы две последовательности X и Y , и задача состоит в том, чтобы найти кратчайшую общую суперсимметрию этих последовательностей. В общем, scs не уникален.

Для двух последовательностей X = <x1,...,xm> и Y = <y1,...,yn> последовательность U = <u1,...,uk> является общей суперпоследовательностью X и Y если U - суперпоследовательность как X и Y Другими словами, кратчайшая общая суперпоследовательность строк x и y является кратчайшей строкой z такой, что x и y являются подпоследовательностями z .

Для двух входных последовательностей scs можно легко сформировать из самой длинной общей подпоследовательности (lcs). Например, если X[1..m]=abcbdab и Y[1..n]=bdcaba , Y[1..n]=bdcaba - Z[1..r]=bcba . Вставляя символы не-lcs при сохранении порядка символов, получаем scs: U[1..t]=abdcabdab .

Совершенно очевидно, что r+t=m+n для двух входных последовательностей. Однако для трех или более входных последовательностей это не выполняется. Заметим также, что проблемы lcs и scs не являются двойственными проблемами.

Для более общей проблемы нахождения строки S являющейся суперструной множества строк S1,S2,...,Sl , проблема NP-Complete. Также можно найти хорошие приближения для среднего случая, но не для наихудшего случая.

Пример кратчайшей общей проблемы суперсимметрии:

Сложность времени: O(max(m,n))

Реализация самой короткой общей проблемы суперсимметрии в 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);
    }
}