【C++】文字列を別の文字列へ変換するために必要な最小の削除・挿入回数を求める方法

問題の概要

大きさがそれぞれ m と n の2つの文字列 str1 と str2 が与えられたとします。ここで求めたいのは、str1 を str2 に変換するために必要な「削除」と「挿入」の操作回数を最小化するという課題です。

例として、次のようなケースを考えてみましょう。

Str1 = "tutorialspoint"
Str2 = "tutorials"
str1 を str2 に変換するには、5文字分の削除、つまり
str1 から "point" を取り除く必要があります。

解法の考え方:最長共通部分列(LCS)

この問題は、最長共通部分列(Longest Common Subsequence:LCS) を利用することで効率的に解くことができます。LCSとは、2つの文字列に共通して現れる部分列のうち、最も長いものを指します。

両方の文字列に共通する部分は削除や挿入の対象から外せるため、LCSの長さを lcsSize とおくと、必要な操作回数は次のように表せます。

• 削除が必要な文字数 = str1 の長さ − lcsSize
• 挿入が必要な文字数 = str2 の長さ − lcsSize

アルゴリズムの手順

1. str1 と str2 の最長共通部分列(LCS)を求める。その長さを lcsSize とする
2. 削除すべき文字数 = (str1 の長さ − lcsSize)
3. 挿入すべき文字数 = (str2 の長さ − lcsSize)

C++による実装例

以下は、再帰的にLCSを求め、そこから最小の削除・挿入回数を計算するC++プログラムです。

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

// s1 と s2 の最長共通部分列(LCS)の長さを再帰的に求める
int lcs(string s1, string s2, int m, int n){
    if (m == 0 || n == 0) {
        return 0;
    }
    if (s1[m - 1] == s2[n - 1]) {
        return 1 + lcs(s1, s2, m - 1, n - 1);
    } else {
        return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
    }
}

void minDeletionAndInsertion(string s1, string s2){
    int m = s1.size();
    int n = s2.size();
    int lcsSize = lcs(s1, s2, m, n);
    cout << "Min deletion = " << (m - lcsSize) << endl;
    cout << "Min insertion = " << (n - lcsSize) << endl;
}

int main(){
    minDeletionAndInsertion("tutorialspoint", "tutorials");
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Min deletion = 5
Min insertion = 0

"tutorialspoint"(14文字)と "tutorials"(9文字)のLCSは "tutorials" そのものなので lcsSize = 9 となります。したがって、削除は 14 − 9 = 5 回、挿入は 9 − 9 = 0 回という結果になります。

計算量に関する補足

上記のような素朴な再帰実装では、最悪の場合の時間計算量が O(2^m+n) となり、文字列が長くなると処理が非常に遅くなります。実用的な場面では、動的計画法(DP) を用いてメモ化テーブルを構築することで、O(m × n) の時間・空間計算量でLCSを求めるのが一般的です。これにより、長い文字列に対しても高速に最小の削除・挿入回数を算出できます。