C++で文字列の異なる部分列の数を数える方法（動的計画法）

この記事では、2つの文字列 S と T が与えられたとき、S の部分列のうち T と一致するものが何通りあるかを数える問題を、C++と動的計画法（DP）を使って解く方法を解説します。

部分列（サブシーケンス）とは？

部分列とは、元の文字列から一部の文字（0個でも可）を削除して作られる新しい文字列のことであり、残った文字の相対的な順序は崩れません。例えば、「ACE」は「ABCDE」の部分列ですが、「AEC」は順序が入れ替わっているため部分列にはなりません。

問題の例

入力として「baalllloonnn」と「balloon」が与えられた場合、T に一致する S の部分列は 36通り 存在します。

解き方のアルゴリズム

以下の手順で動的計画法によりこの問題を解きます。

1. n を s の長さ、m を t の長さとします。インデックスを扱いやすくするため、s と t の先頭に空白を連結しておきます。
2. (n + 1) × (m + 1) のサイズを持つ行列 dp を作成します。
3. dp[0][0] := 1 とし、さらに 0 列目のすべての行に 1 を設定します。
4. i を 1 から n まで繰り返します。
   • j を 1 から m まで繰り返します。
     • s[i] == t[j] の場合、dp[i][j] := dp[i - 1][j - 1]
     • dp[i][j] := dp[i][j] + dp[i - 1][j]
5. 最後に dp[n][m] を返します。

動的計画法の考え方

ここで dp[i][j] は「s の先頭 i 文字から作れる部分列のうち、t の先頭 j 文字と一致するものの個数」を意味します。空文字列を作る方法は常に 1 通りしかないため、dp[i][0] = 1 となります。s[i] と t[j] が一致する場合は、その文字を採用するケース（dp[i-1][j-1]）と採用しないケース（dp[i-1][j]）の合計が答えになります。一方、一致しない場合はその文字を採用できないため、dp[i-1][j] の値をそのまま引き継ぎます。

C++での実装例

それでは、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();
        s = " " + s;
        t = " " + t;
        vector < vector <lli> > dp(n + 1, vector <lli> (m + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++)dp[i][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
                dp[i][j]+= dp[i - 1][j];
            }
        }
        return dp[n][m];
    }
};
main(){
    Solution ob;
    cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

入力

"baalllloonnn"
"balloon"

出力

36

このように、動的計画法を用いることで、一見膨大な組み合わせになりそうな部分列の数え上げも、O(n × m) の計算量で効率的に求めることができます。