algorithm
最短共通問題

最短共通共通計画問題基本情報

最短共通スーパーシーケンスは、このタスクの外部関数として使用できる最も長い共通サブシーケンスに密接に関連する問題です。最短共通スーパーシーケンス問題は、最も長い共通サブシーケンス問題に密接に関連する問題である。

最短の共通スーパーシーケンス（scs）は最小の長さの共通のスーパーシーケンスです。最短の共通スーパーシーケンス問題では、2つのシーケンスXとYが与えられ、タスクはこれらのシーケンスの可能な最短の共通スーパーシーケンスを見つけることである。一般的に、scは一意ではありません。

与えられた二つの配列X = <x1,...,xm>およびY = <y1,...,yn>シーケンスU = <u1,...,uk>の一般的なスーパーシーケンスであるXとYの場合は、 UはXとYスーパーシーケンスです。換言すれば、文字列の最短の共通スーパー配列x及びy最短の文字列であり、 zの両方ように、 x及びyのサブシーケンスであるz 。

2つの入力シーケンスに対して、最も長い共通部分シーケンス（lcs）から容易にscsを形成することができる。例えば、 X[1..m]=abcbdabかつY[1..n]=bdcaba場合、lcsはZ[1..r]=bcba 。記号の順番を保ったまま非lcsシンボルを挿入すると、sc U[1..t]=abdcabdab 。

2つの入力シーケンスに対して、 r+t=m+nであることは明らかである。しかし、3つ以上の入力シーケンスの場合、これは成立しません。 lcsとscsの問題は二重の問題ではないことにも注意してください。

ストリングS1,S2,...,SlセットのスーパーストリングであるストリングSを見つけるより一般的な問題については、問題はNP完全です。また、平均的な場合には良好な近似が見出されるが、最悪の場合には見出されない。

最短共通共起問題の例：

時間複雑度： 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);
    }
}