C++で2つの文字列に共通する部分列の数を求める方法

本記事では、文字 str1 と str2 の2つの文字列が与えられたとき、両方の文字列に共通する部分列（サブシーケンス）の数を計算する方法を解説します。ここでは動的計画法（Dynamic Programming）を用いて問題を解きます。そのため、まず動的計画法とは何か、どのような問題に適用できるのかを理解しておきましょう。

動的計画法とは

動的計画法は、問題をより小さな部分問題へと分割していくという点で「分割統治法」と似ています。しかし、分割統治法と異なるのは、各部分問題を独立に解かないという点です。むしろ、小さな部分問題の結果を記憶しておき、類似した、あるいは重複する部分問題に対してその結果を再利用します。

動的計画法は、問題を類似した部分問題に分割でき、その結果を再利用できる場合に有効です。主に最適化問題で使われる手法であり、目の前の部分問題を解く前に、すでに解いた部分問題の結果を確認します。そして、それらの解を組み合わせることで、最良の解を導き出します。

入力と出力の例

入力 − string str1 = "abc"
        string str2 = "ab"
出力 − count is 3

説明： 与えられた文字列から作られる共通部分列は { 'a', 'b', 'ab' } の3つです。

入力 − string str1 = "ajblqcpdz"
        string str2 = "aefcnbtdi"
出力 − count is 11

共通部分列： { "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd", "acd" } の11個となります。

アルゴリズムのアプローチ

• 2つの文字列 str1 と str2 を入力として受け取ります。
• length() 関数を使って各文字列の長さを取得し、str1 の長さを len1、str2 の長さを len2 に格納します。length() 関数は文字列内の文字数に応じた整数値を返します。
• 動的計画法を実装するための2次元配列 arr[len1+1][len2+1] を作成します。
• i を 0 から len1 未満までループさせます。
• その内側で、j を 0 から len2 未満までループさせます。
• ループ内で、str1[i-1] == str2[j-1] である場合、arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j] を設定します。
• そうでない場合は、arr[i][j] = arr[i][j-1] + arr[i-1][j] − arr[i-1][j-1] を設定します。
• 最後に arr[len1][len2] を返します。
• 結果を出力します。

C++コード例

#include <iostream>
using namespace std;
// 文字列内の部分列の数をカウントする関数
int countsequences(string str, string str2){
    int n1 = str.length();
    int n2 = str2.length();
    int dp[n1+1][n2+1];
    // 配列の初期化
    for (int i = 0; i <= n1; i++){
        for (int j = 0; j <= n2; j++){
            dp[i][j] = 0;
        }
    }
    // str の各文字について処理
    for (int i = 1; i <= n1; i++){
        // str2 の各文字について処理
        for (int j = 1; j <= n2; j++){
            // 両方の文字列で文字が一致する場合
            if (str[i - 1] == str2[j - 1]){
                dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
            }
            else{
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
            }
        }
    }
    return dp[n1][n2];
}
int main(){
    string str = "abcdejkil";
    string str2 = "bcdfkaoenlp";
    cout << "count is: " << countsequences(str, str2) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

count is: 51

このように、動的計画法を用いることで、2つの文字列に共通する部分列の総数を効率的に求めることができます。計算量は O(n1 × n2) となり、文字列の長さが増えても現実的な時間で処理可能です。