algorithm
최단 공통 보완 문제

최단 공통 보완 문제 문제 기본 정보

최단 공통 수퍼 시퀀스 는 가장 긴 공통 서브 시퀀스 와 밀접하게 관련된 문제로,이 작업을위한 외부 함수로 사용할 수 있습니다. 가장 짧은 공통 수퍼 시퀀스 문제는 가장 긴 공통 서브 시퀀스 문제와 밀접한 관련이있는 문제입니다.

가장 짧은 공통 수퍼 시퀀스 (scs)는 최소 길이의 공통 수퍼 시퀀스입니다. 최단 공통 수퍼 스컨스 문제에서 두 시퀀스 X 와 Y 가 주어지며이 시퀀스의 가능한 가장 짧은 수퍼 시퀀스를 찾아야합니다. 일반적으로 scs는 고유하지 않습니다.

두 시퀀스 X = <x1,...,xm> 과 Y = <y1,...,yn> 주어지면 시퀀스 U = <u1,...,uk> 는 X 와 Y 의 공통 수퍼 시퀀스이다. if U 는 X 와 Y 의 수퍼 시퀀스입니다. 즉, 스트링의 최단 공통 수퍼 시퀀스 x 및 y 가장 짧은 캐릭터 인 z 모두되도록 x 및 y 서브 시퀀스이다 z .

두 입력 시퀀스의 경우, 가장 긴 공통 부분 시퀀스 (scs)가 쉽게 형성 될 수 있습니다 (lcs). 예를 들어, X[1..m]=abcbdab 이고 Y[1..n]=bdcaba 이면 lcs는 Z[1..r]=bcba 입니다. 기호 순서를 유지하면서 non-lcs 기호를 삽입하면 U[1..t]=abdcabdab .

2 개의 입력 시퀀스에 대해 r+t=m+n 분명하다. 그러나 세 개 이상의 입력 시퀀스에 대해서는 이것이 적용되지 않습니다. lcs 및 scs 문제는 이중 문제가 아니라는 점에 유의하십시오.

문자열 S1,S2,...,Sl 스트링 인 문자열 S 를 찾는보다 일반적인 문제는 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);
    }
}