C++で最長共通部分列（LCS）をすべて辞書式順序に出力する方法

この記事では、2つの文字列 str1 と str2 が与えられたとき、それらの最長共通部分列（LCS：Longest Common Subsequence）をすべて辞書式順序で出力するC++プログラムの作成方法を解説します。

問題の例

具体的な入力と出力の例を見てみましょう。

入力：str1 = "gfare"、str2 = "rfare"

出力：fare

この場合、"fare" が両方の文字列に共通する最長の部分列となり、これが出力結果となります。

解決アプローチ

この問題は次の手順で解くことができます。

1. LCSの長さを求める：動的計画法（DP）を用いたメモ化再帰により、最長共通部分列の長さを計算し、結果を二次元配列（DPテーブル）にキャッシュします。
2. 辞書式順序ですべてのLCSを出力する：文字を「a」から「z」の順に試しながら再帰的に列を構築し、条件を満たすすべての最長共通部分列を出力します。

文字を「a」から「z」の順で探索するため、出力は自動的に辞書式順序になります。また、その文字を選んだ場合に残りの部分でLCSの長さを満たせるかどうかを事前に確認することで、無駄な探索を効率的に枝刈りできます。

C++での実装例

コードのポイント

• calcLCSLenght()：メモ化再帰により、位置 i・j 以降のLCSの長さを求める関数です。計算済みの値はDPテーブルから取得するため高速に動作します。
• printAllLCS()：現在の列の長さがLCSの長さに達したら結果を出力し、そうでなければ各文字を「a」〜「z」の順に検証して再帰的に列を伸ばしていきます。
• main()：DPテーブルを初期化し、LCSの長さを算出した後、すべての最長共通部分列の出力を行います。

以下が実際のサンプルコードです。

#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

入力文字列 "xysxysx" と "xsyxsyx" の場合、6つの異なる最長共通部分列が存在し、いずれも5文字の長さを持つことがわかります。出力はすべて辞書式順序に正しく並んでいます。