C++でターゲット文字列と一致する部分列の数を求めるプログラム

2つの小文字のみで構成された文字列 s と t が与えられたとします。このとき、s の部分列（サブシーケンス）のうち、t と完全に一致するものが何通りあるかを求めます。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。

問題例

入力が s = "abbd"、t = "bd" の場合、出力は 2 になります。「bd」という部分列は次の2通りの組み合わせで作れるからです。

• s[1] と s[3] を連結する
• s[2] と s[3] を連結する

解法のアルゴリズム

この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。

• 剰余計算用の定数 m := 10^9 + 7 を用意する
• t の長さが 0 の場合は 0 を返す
• t が s と完全に一致する場合は 1 を返す
• t の長さが s の長さより大きい場合は 0 を返す
• t の長さ + 1 のサイズを持つ配列 table を定義し、すべて 0 で初期化する
• table[0] := 1 とする（空の部分列は1通りとみなす）
• i を 0 から s の長さ - 1 まで繰り返す：
  • onsave := table のコピーを作成する
  • j を 0 から table のサイズ - 1 まで繰り返す：
    • s[i] が t[j] と一致する場合、table[j + 1] = (table[j + 1] mod m + onsave[j] mod m) で更新する

最後に table[t の長さ] の値を m で割った余りを返せば、それが求める個数になります。

アルゴリズムのポイント

配列 table[j] は、「これまで処理した s の文字を使って、t の先頭 j 文字分を作る方法の数」を表しています。文字 s[i] が t[j] と一致したタイミングで、その文字を採用するケースの数（onsave[j]）を table[j + 1] に加算していきます。各ループの前に table のコピー（onsave）を取ることで、同一ループ内の更新の影響を受けずに正しく計算できるのがポイントです。時間計算量は O(|s| × |t|) となります。

理解を深めるために、以下の実装例を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
    int m = 1000000007;
    if (t.size() == 0)
        return 0;
    if (t == s)
        return 1;
    if (t.size() > s.size())
        return 0;
    vector<int> table(t.size() + 1, 0);
    table[0] = 1;
    for (int i = 0; i < s.size(); i++) {
        vector<int> onsave = table;
        for (int j = 0; j < table.size(); j++) {
            if (s[i] == t[j]) {
                table[j + 1] = (table[j + 1] % m + onsave[j] % m) % m;
            }
        }
    }
    return table[t.size()] % m;
}
main(){
    string s = "abbd", t = "bd";
    cout << (solve(s, t));
}

入力

"abbd", "bd"

出力

2