C++で2つの文字列を同一にするための最小コスト

2つの文字列 A と B、そしてそれぞれのコスト値 CostA と CostB が与えられているとします。このとき、A と B を同一にするために必要な最小コストを求めるのが本問題です。

文字列からは自由に文字を削除でき、文字列 A から1文字削除するたびに CostA、文字列 B から1文字削除するたびに CostB のコストがかかります。どの文字を削除してもコストは一定です。

例として、文字列 A = "wxyz"、B = "wyzx"、CostA = 10、CostB = 20 の場合を考えてみましょう。両方の文字列から「x」を削除すると、A と B はどちらも "wyz" となり一致します。このときのコストは 10 + 20 = 30 となり、これが出力結果となります。

解法のアプローチ：最長共通部分列（LCS）

この問題は、古典的な最長共通部分列（Longest Common Subsequence: LCS）問題の応用形です。考え方は以下の通りです。

1. A と B の LCS の長さを求める。
2. A から削除すべき文字数は「A の長さ − LCS の長さ」。
3. B から削除すべき文字数は「B の長さ − LCS の長さ」。
4. 最小コスト =（A から削除する文字数 × CostA）＋（B から削除する文字数 × CostB）。

LCS に含まれる文字はそのまま残せばよいため、削除が必要なのは共通部分に含まれない文字だけです。動的計画法を使えば LCS を効率的に計算できます。

C++での実装例

#include <iostream>
#include <string>
using namespace std;

int minCostToMakeIdentical(string A, string B, int costA, int costB) {
    int m = A.length();
    int n = B.length();
    int dp[m + 1][n + 1];

    // 動的計画法でLCSの長さを求める
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    int lcs = dp[m][n];
    // 削除した文字数にそれぞれのコストを掛けて合計
    return (m - lcs) * costA + (n - lcs) * costB;
}

int main() {
    string A = "wxyz";
    string B = "wyzx";
    int costA = 10, costB = 20;

    cout << "最小コスト: " << minCostToMakeIdentical(A, B, costA, costB);
    return 0;
}

出力

最小コスト: 30

処理の流れの解説

上記の例では、A = "wxyz" と B = "wyzx" の LCS は "wyz"（長さ3）です。したがって、A からは1文字（x）、B からも1文字（x）を削除すればよいことになります。

• A からの削除コスト：(4 − 3) × 10 = 10
• B からの削除コスト：(4 − 3) × 20 = 20
• 合計：10 + 20 = 30

計算量

動的計画法による LCS の計算には O(m × n) の時間計算量と空間計算量が必要です。ここで m と n はそれぞれ文字列 A と B の長さです。文字列の長さが数千程度であれば十分に実用的な速度で動作します。