C++で解く最短共通超列：2つの文字列を部分列として含む最短のスーパーシーケンスを求めるプログラム

本記事では、2つの文字列を部分列（サブシーケンス）として同時に含む、最も短い文字列――すなわち最短共通超列（Shortest Common Supersequence）――を求めるC++プログラムを解説します。この問題は、動的計画法（DP）を活用することで効率的に解くことができます。

最短共通超列とは

ある文字列 X が別の文字列 Y の部分列であるとは、Y から一部の文字を取り除いて（文字の順序は保ったまま）X と同じ並びを作れることを意味します。例えば「ACD」は「ABCDE」の部分列です。2つの文字列 A と B の両方を部分列として含む文字列を「超列」と呼び、その中で最も短いものが最短共通超列となります。その長さは「|A| + |B| − LCS(A, B)」（LCS は最長共通部分列の長さ）で求められます。

アルゴリズム

まず、二次元配列 ss[i][j] に「A[0 .. i-1] と B[0 .. j-1] に対する最短超列の長さ」をボトムアップ方式で計算しながら格納していきます。遷移式は以下の通りです。

• i == 0 のとき：ss[i][j] = j（A が空なら、残りは B の文字すべてが必要）
• j == 0 のとき：ss[i][j] = i（B が空なら、残りは A の文字すべてが必要）
• A[i-1] == B[j-1] のとき：ss[i][j] = 1 + ss[i-1][j-1]（共通の文字は1回だけ使えばよい）
• それ以外のとき：ss[i][j] = 1 + min(ss[i-1][j], ss[i][j-1])

続いて、完成したDP表を後ろからたどることで、実際の超列の文字列を復元します。

1. 結果を格納する文字列 s を用意し、i = a、j = b で初期化します。
2. i > 0 かつ j > 0 の間、以下を繰り返します。
   ・A と B の現在の文字が同じ場合：その文字は最短超列の一部となるため s に追加し、i・j・index を1ずつ減らします。
   ・ss[i-1][j] > ss[i][j-1] の場合：B の現在の文字を s に追加し、j・index を1ずつ減らします。
   ・それ以外の場合：A の現在の文字を s に追加し、i・index を1ずつ減らします。
3. i > 0 の間、A の残りの文字を s に追加します。
4. j > 0 の間、B の残りの文字を s に追加します。
5. s を反転して返します（後ろから構築しているため）。

C++での実装例

#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];

    // 最短超列の長さをボトムアップで計算
    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;

    // DP表を逆順にたどって超列を復元
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            s.push_back(A[i - 1]);
            i--, j--, index--;
        } else if (ss[i - 1][j] > ss[i][j - 1]) {
            s.push_back(B[j - 1]);
            j--, 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

計算量

時間計算量・空間計算量はいずれも O(a × b) です（a、b はそれぞれ文字列 A、B の長さ）。LCS のDP表をそのまま流用しているため、まず長さを求めてから表を逆走査して文字列を復元する、という2段階の構成になっています。入力サイズが大きい場合は、メモリ使用量の削減や std::string の予約（reserve）による最適化も検討するとよいでしょう。