C++で解く最短共通スーパーシーケンス（最短共通超部分列）の求め方

2つの文字列 str1 と str2 が与えられたとき、その両方を部分列として含む最短の文字列（最短共通スーパーシーケンス）を求める問題を考えます。答えが複数存在する場合は、そのうちの1つを返せばよいことになっています。

ここで、文字列 S が文字列 T の部分列であるとは、T からいくつかの文字（0個でも可）を任意の位置から削除した結果が S と一致することを指します。

例えば、入力が "acab" と "bac" の場合、出力は "bacab" となります。これは、与えられた2つの文字列がどちらも "bacab" の部分列になっているためです。

アルゴリズムの考え方

この問題は、まず最長共通部分列（LCS: Longest Common Subsequence）を動的計画法（DP）で求め、その LCS を「共有部分」として2つの文字列をマージすることで解けます。手順は以下の通りです。

ステップ1：LCS を求める関数 getLCS() を定義する

• 結果を格納する空文字列 ret を用意します。
• n := s1 の長さ、m := s2 の長さとします。
• (n + 1) × (m + 1) のサイズの2次元配列 dp を定義します。
• s1 と s2 の先頭に空白文字を連結し、インデックスを1始まりにします。
• i = 1 から n まで、j = 1 から m まで二重ループを回します。
  • s1[i] と s2[j] が一致する場合：dp[i][j] := 1 + dp[i-1][j-1]
  • 一致しない場合：dp[i][j] := max(dp[i-1][j], dp[i][j-1])

ステップ2：DPテーブルを逆traceしてLCS文字列を復元する

• i と j がどちらも0でない間、以下を繰り返します。
  • dp[i][j] == dp[i-1][j] なら i を減らしてスキップ。
  • dp[i][j] == dp[i][j-1] なら j を減らしてスキップ。
  • それ以外の場合、ret に s1[i] を追加し、i と j を両方減らします。
• 最後に ret を反転して返します（後ろから辿っているため）。

ステップ3：LCSを基準に2つの文字列をマージする

• s3 := getLCS(str1, str2) としてLCSを取得します。
• ret := 空文字列、i := 0、j := 0、k := 0 と初期化します。
• k が s3 のサイズ未満の間、以下を繰り返します。
  • i が str1 の範囲内かつ str1[i] != s3[k] なら、ret に str1[i] を追加して i++。
  • j が str2 の範囲内かつ str2[j] != s3[k] なら、ret に str2[j] を追加して j++。
  • それ以外の場合、ret に s3[k] を追加し、i・j・k をすべて1増やします。
• ループ終了後、str1 と str2 の残りの文字をそれぞれ ret に追加します。
• ret を返します。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string shortestCommonSupersequence(string str1, string str2){
        string s3 = getLCS(str1, str2);
        string ret = "";
        int i = 0;
        int j = 0;
        int k = 0;
        while (k < s3.size()) {
            if (i < str1.size() && str1[i] != s3[k]) {
                ret += str1[i];
                i++;
                continue;
            }
            if (j < str2.size() && str2[j] != s3[k]) {
                ret += str2[j];
               j++;
                continue;
            }
            ret += s3[k];
            k++;
            i++;
            j++;
        }
        while (i < str1.size()) {
            ret += str1[i];
            i++;
        }
        while (j < str2.size()) {
            ret += str2[j];
            j++;
        }
        return ret;
    }
    string getLCS(string s1, string s2){
        string ret = "";
        int n = s1.size();
        int m = s2.size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
        int i = n;
        int j = m;
        s1 = " " + s1;
        s2 = " " + s2;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        while (i && j) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
                continue;
            }
            if (dp[i][j] == dp[i][j - 1]) {
                j--;
                continue;
            }
            ret += s1[i];
            i--;
            j--;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.shortestCommonSupersequence("acab", "bac"));
}

入力

"acab", "bac"

出力

bacab

計算量について

LCSを求めるDPテーブルの構築に O(n × m)、バックトラックにも O(n + m) しかかからないため、全体の計算量は O(n × m)、必要なメモリも DP テーブル分の O(n × m) となります。この手法は LeetCode の「Shortest Common Supersequence」などの典型的な動的計画法の練習問題として知られており、LCSへの理解を深める良い題材です。