最短共通超部分列（SCS）とは？動的計画法で長さを求めるアルゴリズムをC++で解説

最短共通超部分列（Shortest Common Supersequence、略称：SCS）とは、与えられた2つの列のすべての要素が含まれる列のことです。言い換えると、元となる2つの文字列がどちらも、この超部分列の部分列となっている関係です。

2つの文字列に共通する文字が1つもない場合には、単純に連結するだけで超部分列が得られます。しかし、共通の文字が含まれている場合は、まず最長共通部分列（LCS）を見つけたうえで、もう一方の文字列の残りの文字を付け足していく必要があります。

なお、SCSの長さは次の式でも求められます。

SCSの長さ = len(str1) + len(str2) − LCSの長さ

入力と出力の例

入力：
2つの文字列「ABCDEF」と「XYDEF」
出力：
最短共通超部分列の長さ
ここでの超部分列は「ABCDEFXY」となり、長さは8です。

アルゴリズムの流れ

入力： 2つの文字列 str1 と str2

出力： 最短共通超部分列の長さ

Begin
    m := str1 の文字数
    n := str2 の文字数
    サイズ (m+1) × (n+1) の表 seqTab を定義

    for i := 0 to m, do
        for j := 0 to n, do
            if i = 0 のとき
                seqTab[i, j] := j        // 片方が空なら相手の長さがそのまま答え
            else if j = 0 のとき
                seqTab[i, j] := i        // 同上
            else if str1[i-1] = str2[j-1] のとき
                seqTab[i, j] := 1 + seqTab[i-1, j-1]   // 文字が一致した場合
            else
                seqTab[i, j] := 1 + min(seqTab[i-1, j], seqTab[i, j-1])
        done
    done
    return seqTab[m, n]
End

このアルゴリズムは動的計画法（DP）を用いており、計算量は O(m × n)、必要な記憶領域も同様に O(m × n) となります。

遷移のポイント

• 片方の文字列が空の場合： もう一方の文字列全体がそのまま超部分列になるため、その長さをそのまま格納します。
• 現在比較中の文字が一致する場合： その文字は両方の文字列で共有できるため、斜め左上の値に1を加えたものになります。
• 文字が一致しない場合： どちらかの文字列から1文字採用するため、「上のセル」「左のセル」の小さい方に1を加えます。

C++による実装例

#include<iostream>
using namespace std;

int min(int a, int b) {
    return (a<b)?a:b;
}

int superSeq(string str1, string str2) {
    int m = str1.size();
    int n = str2.size();

    int supSeqTable[m+1][n+1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (!i)
                supSeqTable[i][j] = j;      // 片方が空なら長さはj
            else if (!j)
                supSeqTable[i][j] = i;      // 同様に長さはi
            else if (str1[i-1] == str2[j-1])
                supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];   // 文字が一致
            else
                supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);
        }
    }
    return supSeqTable[m][n];
}

int main() {
    string first = "ABCDEF";
    string second = "XYDEF";
    cout << "Length of the shortest supersequence is " << superSeq(first, second);
}

実行結果

Length of the shortest supersequence is 8

まとめ

最短共通超部分列の問題は、LCS（最長共通部分列）の知識があると理解しやすいのが特徴です。「2つの文字列の合計の長さから共通部分の重複分を引く」という発想で捉えると、DPテーブルの更新式の意味も自然に見えてきます。文字列処理や差分マージなど、実際の応用場面も多いため、ぜひ実装を通じて仕組みを身につけてください。