두 개 이상의 시퀀스를 부분 시퀀스로 포함하는 최단 슈퍼 시퀀스를 찾는 C++ 프로그램

이 글에서는 두 개 이상의 시퀀스(문자열)를 부분 시퀀스(subsequence) 형태로 모두 포함하면서 길이가 가장 짧은 최단 슈퍼 시퀀스(Shortest Supersequence)를 찾는 C++ 프로그램을 살펴봅니다.

최단 슈퍼 시퀀스란?

최단 슈퍼 시퀀스란 주어진 두 문자열 A와 B를 각각 부분 시퀀스로서 모두 포함하는 문자열 중 길이가 가장 짧은 것을 말합니다. 이 문제는 최장 공통 부분 시퀀스(LCS)와 밀접한 관련이 있으며, 최단 슈퍼 시퀀스의 길이는 a + b - LCS(A, B)로 계산할 수 있습니다. 아래에서는 동적 계획법(Dynamic Programming)을 활용해 이를 효율적으로 구현합니다.

알고리즘

시작
    함수 ShortestSubSeq()는 A와 B의 슈퍼 시퀀스를 반환한다:
    1) A[0 .. i-1]과 B[0 .. j-1]에 대한 최단 슈퍼 시퀀스의 길이를 저장하는 2차원 배열 ss[i][j]를 선언한다.
    2) 바텀업(bottom-up) 방식의 점화식을 이용해 가능한 슈퍼 시퀀스의 길이를 구한다.
    3) 각 인덱스 위치에서의 최단 슈퍼 시퀀스 길이를 저장하는 배열 ss[i][j]를 선언한다.
    4) 최단 슈퍼 시퀀스를 저장할 문자열 s를 선언한다.
    5) i = a, j = b로 초기화한다.
    6) while (i > 0 && j > 0)
        A) A와 B의 현재 문자가 같다면, 그 문자는 최단 슈퍼 시퀀스의 일부이다.
           결과에 현재 문자를 추가하고, i, j, index 값을 감소시킨다.
        B) 그렇지 않고 A와 B의 현재 문자가 다르다면,
           B의 현재 문자를 결과에 추가하고, j와 index 값을 감소시킨다.
        C) 위 조건에 해당하지 않으면,
           A의 현재 문자를 결과에 추가하고, i와 index 값을 감소시킨다.
    7) while (i > 0)
        A의 남은 문자들을 결과 문자열에 추가한다.
    8) while (j > 0)
        B의 남은 문자들을 결과 문자열에 추가한다.
    9) 문자열을 뒤집어서 반환한다.
끝

예제 코드

#include <bits/stdc++.h>
using namespace std;
string ShortestSuperSeq(string A, string B) {
   int a = A.length();  
   int b = B.length();
   int ss[a + 1][b + 1];
   // DP 테이블 채우기: 각 위치에서의 최단 슈퍼 시퀀스 길이 계산
   for (int i = 0; i <= a; i++) {
      for (int j = 0; j <= b; j++) {
         if(i == 0)
            ss[i][j] = j;
         else if(j == 0)
            ss[i][j] = i;
         else if(A[i - 1] == B[j - 1])
            ss[i][j] = 1 + ss[i - 1][j - 1];
         else
            ss[i][j] = 1 + min(ss[i - 1][j], ss[i][j - 1]);
      }
   }
   int index = ss[a][b];
   string s;
   int i = a, j = b;
   // 역추적(tracing back)을 통해 실제 슈퍼 시퀀스 문자열 구성
   while (i > 0 && j > 0) {
      // A와 B의 현재 문자가 같다면, 그 문자는 최단 슈퍼 시퀀스의 일부이다
      if (A[i - 1] == B[j - 1]) {
         // 결과에 현재 문자를 추가하고 i, j, index 값을 감소시킨다
         s.push_back(A[i - 1]);
         i--, j--, index--;
      }
      // A와 B의 현재 문자가 다른 경우
      else if (ss[i - 1][j] > ss[i][j - 1]) {
         // B의 현재 문자를 결과에 추가하고 j, index 값을 감소시킨다
         s.push_back(B[j - 1]);
         j--, index--;
      }
      // A의 현재 문자를 결과에 추가하고 i, index 값을 감소시킨다
      else {
         s.push_back(A[i - 1]);
         i--, index--;
      }
   }
   // A의 남은 문자들을 결과 문자열에 추가한다
   while (i > 0) {
      s.push_back(A[i - 1]);
      i--, index--;
   }
   // B의 남은 문자들을 결과 문자열에 추가한다
   while (j > 0) {
      s.push_back(B[j - 1]);
      j--, index--;
   }
   reverse(s.begin(), s.end()); // 문자열을 뒤집고 반환한다
   return s;
}
int main() {
   string M = "ABBCDDEEFF";
   string N = "ABCDEEEFF";
   cout <<"The Shortest SuperSequence is:"<< ShortestSuperSeq(M, N);
   return 0;
}

실행 결과

The Shortest SuperSequence is:ABBCDEDEEFF

정리

위 프로그램은 동적 계획법 테이블을 먼저 완성한 뒤, 역추적(backtracking) 방식으로 실제 최단 슈퍼 시퀀스 문자열을 구성합니다. 시간 복잡도는 O(a × b), 공간 복잡도 역시 O(a × b)로, 두 문자열의 길이 곱에 비례합니다. 이 접근 방식은 LCS 기반 문제뿐 아니라 문자열 병합, diff 알고리즘 등 다양한 응용 분야에 활용될 수 있습니다.