C++で2つ目の文字列の文字を入れ替えた後、2つの文字列の最長共通プレフィックスを求める方法

2つの文字列 str1 と str2 が与えられたとします。2つ目の文字列に対して「任意の2文字を入れ替える」という操作を0回以上行った後、両者の間で最長の共通プレフィックス(接頭辞)の長さを求めるのがこの問題です。

例えば、str1 = "HERE"、str2 = "THERE" の場合、出力は 4 になります。2つ目の文字列は文字を入れ替えることで "HERET" に変換できるため、先頭から一致する部分の長さは4文字となるからです。

アプローチ

文字の入れ替えは str2 に対してしか行えないため、プレフィックスの長さを最大化するには、次のような考え方でアルゴリズムを組み立てます。

1. まず str2 に含まれる各文字の出現回数を、サイズ26の頻度配列に記録します。
2. 次に str1 を先頭から走査し、現在注目している文字が str2 側にまだ残っている(頻度が0より大きい)かどうかを確認します。
3. 残っていればカウントを1増やし、該当文字の頻度を1減らして次の文字へ進みます。
4. 頻度が0の文字に到達した時点で処理を打ち切り、そこまで一致した文字数を答えとして出力します。

この方法なら、各文字列を1回ずつ走査するだけでよいため、計算量は O(n + m)(n、m はそれぞれの文字列の長さ)と非常に効率的です。

実装例(C++)

#include <iostream>
using namespace std;

void longestPrefix(string str1, string str2) {
    int frequency[26] = {0};          // 各文字の出現回数を記録する配列
    int a = str1.length();
    int b = str2.length();

    // str2 の各文字の出現回数をカウント
    for (int i = 0; i < b; i++) {
        frequency[str2[i] - 97] += 1;
    }

    int c = 0;                        // 一致したプレフィックスの長さ
    for (int i = 0; i < a; i++) {
        if (frequency[str1[i] - 97] > 0) {
            c += 1;                   // 文字が使えるのでカウントを増やす
            frequency[str1[i] - 97] -= 1;
        } else
            break;                    // 使える文字がなければ終了
    }
    cout << "Length of longest common prefix: " << c;
}

int main() {
    string str1 = "here", str2 = "there";
    longestPrefix(str1, str2);
}

出力

Length of longest common prefix: 4

コードのポイント

この実装の鍵となるのは frequency 配列 です。str2 の文字は自由に並べ替えられるため、プレフィックスを構成できるかどうかは「位置」ではなく「各文字が何回使えるか」だけで決まります。str1 を走査しながら対応する文字の残数を1ずつ減らしていくことで、入れ替え後の str2 で実際に先頭から何文字一致させられるかを正確に求められます。

なお、このコードは英小文字(97〜122のASCIIコード)を前提としています。大文字や記号を扱う場合は、配列サイズを拡張するか、文字コードのオフセットを調整してください。