Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 두 문자열의 최장 공통 부분 수열(LCS)을 사전순으로 모두 출력하기

이 문제에서는 두 개의 문자열 str1과 str2가 주어집니다. 우리의 목표는 사전순(lexicographical order)으로 가장 긴 공통 부분 수열(Longest Common Subsequence)을 모두 출력하는 프로그램을 작성하는 것입니다.

문제 예시

입력: str1 = "gfare", str2 = "rfare"
출력: fare

위 예시에서 두 문자열의 최장 공통 부분 수열은 길이가 4인 "fare" 하나입니다. 하지만 최장 공통 부분 수열은 여러 개 존재할 수 있으며, 그런 경우에는 중복 없이 모든 수열을 사전순으로 출력해야 합니다.

해결 접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

  1. LCS 길이 계산: 동적 계획법(Dynamic Programming)을 활용하여 재귀 함수와 메모이제이션(memoization)으로 두 문자열의 최장 공통 부분 수열 길이를 구하고, 그 결과를 2차원 DP 배열에 저장합니다. 한 번 계산된 값은 재활용되므로 지수 시간이 걸리는 완전 탐색보다 훨씬 효율적입니다.
  2. 사전순 출력: 백트래킹(backtracking) 기법으로 'a'부터 'z'까지 문자를 차례대로 검사합니다. 특정 위치 (i, j)에서 문자 ch를 선택했을 때, 그 위치에서 시작하는 LCS 길이가 앞으로 채워야 할 길이와 일치한다면 해당 문자를 결과 버퍼에 추가하고 재귀 호출을 진행합니다. 'a'부터 'z' 순서로 탐색하기 때문에 별도의 정렬 과정 없이 자연스럽게 사전순에 가까운 결과를 얻을 수 있습니다.

코드에서 calcLCSLenght 함수는 (i, j) 위치에서 시작하는 LCS의 길이를 반환하고, printAllLCS 함수는 이 정보를 활용해 유효한 경로만 따라가며 모든 최장 공통 부분 수열을 생성합니다.

C++ 구현 코드

#include<iostream>
#include<cstring>
#define MAX 100
using namespace std;

int LCSLength = 0;
int DP[MAX][MAX];

int calcLCSLenght(string str1, string str2, int l1, int l2, int i, int j) {
    
    int &lcsLen = DP[i][j];
    if (i==l1 || j==l2)
       return lcsLen = 0;
    if (lcsLen != -1)
       return lcsLen;

    lcsLen = 0;
    
    if (str1[i] == str2[j])
       lcsLen = 1 + calcLCSLenght(str1, str2, l1, l2, i+1, j+1);
    else
       lcsLen = max(calcLCSLenght(str1, str2, l1, l2, i+1, j), calcLCSLenght(str1, str2, l1, l2, i, j+1));
    return lcsLen;
}

void printAllLCS(string str1, string str2, int l1, int l2, char data[], int index1, int index2, int currentLCSlength) {
    if (currentLCSlength == LCSLength) {
        
        data[currentLCSlength] = '\0';
        puts(data);
        return;
    }
    if (index1==l1 || index2==l2)
       return;
    for (char ch='a'; ch<='z'; ch++) {
        
        bool done = false;
        for (int i=index1; i<l1; i++) {
           if (ch==str1[i]) {
              for (int j=index2; j<l2; j++) {
                if (ch==str2[j] && calcLCSLenght(str1, str2, l1, l2, i, j) == LCSLength-currentLCSlength) {
                   data[currentLCSlength] = ch;
                   printAllLCS(str1, str2, l1, l2, data, i+1, j+1, currentLCSlength+1);
                   done = true;
                   break;
                }
              }
           }
           if (done)
              break;
        }
    }
}

int main() {
    
    string str1 = "xysxysx", str2 = "xsyxsyx";
    
    int l1 = str1.length(), l2 = str2.length();
    memset(DP, -1, sizeof(DP));
    LCSLength = calcLCSLenght(str1, str2, l1, l2, 0, 0);
    char data[MAX];
    cout<<"All longest common sub-sequences in lexicographical order are\n";
    printAllLCS(str1, str2, l1, l2, data, 0, 0, 0);
    return 0;
}

실행 결과

All longest common sub-sequences in lexicographical order are
xsxsx
xsxyx
xsysx
xysyx
xyxsx
xyxyx

위 실행 결과를 보면, 입력 문자열 str1 = "xysxysx", str2 = "xsyxsyx"에 대해 길이가 5인 최장 공통 부분 수열이 총 6개 존재하며, 프로그램은 이들을 하나씩 출력합니다. 이처럼 DP 테이블과 백트래킹을 조합하면 최장 공통 부분 수열의 길이 계산과 실제 수열의 열거를 모두 효율적으로 처리할 수 있습니다.